I like this idea. As I mentioned on IRC, I&#39;d call the class Hash rather than Hashable. I&#39;m also with you on the Word return type. It may be less convenient but maybe this will be a tiny step towards the &quot;great Word revolt&quot; (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.<br>
<div><br></div><div><br><div class="gmail_quote">On Thu, Nov 18, 2010 at 5:05 PM, Johan Tibell <span dir="ltr">&lt;<a href="mailto:johan.tibell@gmail.com">johan.tibell@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hi all,<br>
<br>
This is a request for early feedback on something that I&#39;d like to<br>
propose for the next major HP release.<br>
<br>
Milan Straka showed [1] that it&#39;s possible to design a persistent set<br>
(and thus also map) for string-like keys that&#39;s about twice as fast as<br>
the current Data.Set using hashing and a Patricia tree (i.e. IntMap).<br>
The Clojure community has also managed to create a fast persistent<br>
map, based on Bagwell&#39;s hash array mapped trie.<br>
<br>
I&#39;d like to propose that we get the necessary infrastructure in place<br>
for creating fast and easy to use hash-based data structure. Here&#39;s<br>
what I think is needed:<br>
<br>
* A type class for things that can be hashed, Hashable.<br>
<br>
class Hashable a where<br>
 ¬† ¬†hash :: a -&gt; Word<br>
<br>
An alternative would be to have `hash` return an Int, which would make<br>
the method easier to use with Haskell data structures, which are<br>
indexed using Ints, but Word feels like the more correct type to me.<br>
<br>
The Hashable type class would have to go in either base, containers,<br>
or a new package (there&#39;s currently a hashable package on Hackage.)<br>
<br>
* Instances of Hashable for common types, in particular ByteString and Text.<br>
<br>
I already have fast instances for Text and ByteString, based on MurmurHash2 [2].<br>
<br>
* Two new data types in the containers package, Data.HashMap and<br>
Data.HashSet. These would be persistent data structures, initially<br>
based on IntMap, and have the same or similar API to Data.Map and<br>
Data.Set..<br>
<br>
In the future we could also add mutable HashTables, operating in the<br>
ST monad, or other hash-based data types (persistent or mutable).<br>
<br>
Any comments?<br>
<br>
Johan<br>
<br>
1. <a href="http://research.microsoft.com/~simonpj/papers/containers/containers.pdf" target="_blank">http://research.microsoft.com/~simonpj/papers/containers/containers.pdf</a><br>
2. <a href="http://sites.google.com/site/murmurhash/" target="_blank">http://sites.google.com/site/murmurhash/</a><br>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
</blockquote></div><br></div>