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

[Bernie Pope]

2009/8/19 Job Vranish <jvranish at gmail.com>:

>
> 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

It might be the case for IntMap (I haven't checked) that it is better
to do a modify operation than to do a deletion followed by an
insertion on the same key.

One possible improvement is to delay deletions by putting them in a
pending queue. A pending deletion followed by an addItem could be
coalesced into a modify operation on the key to be deleted.

You could even push lookupItems through pending deletions, assuming
that they aren't on the same key (if they are on the same key then the
lookup would fail).

One question is how big should the pending deletion queue be allowed
to become? A long queue might not be a good idea. One problem with
delaying deletions is that it could introduce a space leak (same as
unintended lazy evaluation). Maybe a queue of max length one is
sufficient?

I'm not sure it is worth the trouble, but it might be fun to try.

Cheers,
Bernie.