[Haskell-cafe] Keeping an indexed collection of values?

[Job Vranish]

I've been in a situation a lot lately where I need to keep a collection of
values, and keep track of them by a persistent index.
IO and ST refs can do this, but for various reasons I can't/don't want to
use them.

My first hacked up attempt is as follows:

data IndexedCollection a = IndexedCollection {
    nextKey            :: Int,
    availableKeys :: [Int],
    items                :: (IntMap Int a)
} deriving (Show)

emptyIndexedCollection :: IndexedCollection a
emptyIndexedCollection = IndexedCollection 0 [] empty

addItem :: a -> IndexedCollection a -> (Int, IndexedCollection a)
addItem a (IndexedCollection nextKey' []     t) = (nextKey',
IndexedCollection (nextKey' + 1) [] (insert nextKey' a t))
addItem a (IndexedCollection nextKey' (k:ks) t) = (k, IndexedCollection
nextKey' ks (insert k a t))

removeItem :: Int -> IndexedCollection a -> IndexedCollection a
removeItem k (IndexedCollection nextKey' ks t) = IndexedCollection nextKey'
(k:ks) (delete k t)

lookupItem :: Int -> IndexedCollection a -> Maybe a
lookupItem k (IndexedCollection _ _ t) = lookup k t

Basically: when you add an item, use the first index in availableKeys (if
there is one), otherwise use "nextKey" for the index, and then increment it
for the next item.
When and Item is removed, add it's index to availableKeys

This keeps the code for keeping track of/generating indexes hidden away from
the rest of the program which is nice, and it remains fairly efficient.
Items will be added and removed on very regular basis. Often enough that I'm
slightly concerned about overflow of nextKey for very long run times, and
hence the availableKeys list.

Does anyone know of a better/already existent data structure for handling
this problem?

Or perhaps a better way of keeping a "key pool" than my availableKeys
solution?

- Job
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090818/50d8dd8e/attachment.html