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

[Job Vranish]

Thanks for all the input! :)

My current code (unfinished) is here:
http://github.com/jvranish/IndexedCollection/tree/master
but I think I'll shorten the names as you suggest. (and add some strictness
to availableKeys)

I also added an extra phantom type parameter to the collection (and key) so
that I can prevent keys from being used on different collections even if
they hold elements of the same type.

There is still problem that trying to use a deleted key might return a bad
result rather than an error.
I'm not sure how to fix that one. I could keep another buffer, perhaps of
the last 100 or so deleted keys, so that a key doesn't get recycled until
100 other keys have been freed. This would increase the chances of detecting
this type of error.
I could also possibly integrate it with Bernie's suggestion, which would
probably significantly improve performance in my case. But the added
complexity might not be worth it.

Hmm although... I could potentially do something evil and detect the use of
a deleted key via stableNames. I'd rewrap my keys on recycle so that there
stablenames change.  Then I can check on lookup if the key used has the same
stableName as the key in the collection, if they don't match either raise an
error or return Nothing.
Not sure if I feel that evil though :D

Thanks again for the input :)

- Job


On Fri, Aug 21, 2009 at 7:26 AM, Heinrich Apfelmus <
apfelmus at quantentunnel.de> wrote:

> Heinrich Apfelmus wrote:
> > Job Vranish wrote:
> >> 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.
> >>
> >
> >    module Store (Key, Store, empty, add, delete, lookup) where
> >
> >    newtype Key = Key { int :: Int }
> >
> >    empty  :: Store a
> >    add    :: a -> Store a -> (Key, Store a)
> >    delete :: Key -> Store a -> Store a
> >    lookup :: Key -> Store a -> Maybe a
> >
> > This way, the user doesn't know and care how  Key  is implemented.
> >
> > Last but not least, there is the issue that trying to use an already
> > deleted key might yield a wrong result instead of an error. That
> > shouldn't happen if used correctly, but might give a headache when
> > debugging.
>
> There is even a very simple way to prevent at least some cases of
> misuse, when one key is accidentally used on stores of different type. A
> phantom parameter will do the trick:
>
>    newtype Key a = Key { int :: Int }
>
>    add    :: a -> Store a -> (Key a , Store a)
>    delete :: Key a -> Store a -> Store a
>    lookup :: Key a -> Store a -> Maybe a
>
>
>
> Regards,
> apfelmus
>
> --
> http://apfelmus.nfshost.com
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090821/72257621/attachment.html