RFC: Adding a Hashable type class and HashMap/HashSet data types to HP

[Daniel Peebles]

I like this idea. As I mentioned on IRC, I'd call the class Hash rather than
Hashable. I'm also with you on the Word return type. It may be less
convenient but maybe this will be a tiny step towards the "great Word
revolt" (in which all conceptually unsigned things in the prelude and
standard libraries actually become unsigned) that I hope will occur sometime
in the near future.


On Thu, Nov 18, 2010 at 5:05 PM, Johan Tibell <johan.tibell at gmail.com>wrote:

> Hi all,
>
> This is a request for early feedback on something that I'd like to
> propose for the next major HP release.
>
> Milan Straka showed [1] that it's possible to design a persistent set
> (and thus also map) for string-like keys that's about twice as fast as
> the current Data.Set using hashing and a Patricia tree (i.e. IntMap).
> The Clojure community has also managed to create a fast persistent
> map, based on Bagwell's hash array mapped trie.
>
> I'd like to propose that we get the necessary infrastructure in place
> for creating fast and easy to use hash-based data structure. Here's
> what I think is needed:
>
> * A type class for things that can be hashed, Hashable.
>
> class Hashable a where
>    hash :: a -> Word
>
> An alternative would be to have `hash` return an Int, which would make
> the method easier to use with Haskell data structures, which are
> indexed using Ints, but Word feels like the more correct type to me.
>
> The Hashable type class would have to go in either base, containers,
> or a new package (there's currently a hashable package on Hackage.)
>
> * Instances of Hashable for common types, in particular ByteString and
> Text.
>
> I already have fast instances for Text and ByteString, based on MurmurHash2
> [2].
>
> * Two new data types in the containers package, Data.HashMap and
> Data.HashSet. These would be persistent data structures, initially
> based on IntMap, and have the same or similar API to Data.Map and
> Data.Set..
>
> In the future we could also add mutable HashTables, operating in the
> ST monad, or other hash-based data types (persistent or mutable).
>
> Any comments?
>
> Johan
>
> 1. http://research.microsoft.com/~simonpj/papers/containers/containers.pdf
> 2. http://sites.google.com/site/murmurhash/
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20101118/2af9dcda/attachment.html