[Haskell-cafe] Pure hashtable library

[Jan-Willem Maessen]

On Aug 27, 2008, at 3:41 AM, Bulat Ziganshin wrote:

> Hello haskell-cafe,
>
> solving one more task that uses English dictionary, i've thought:  
> why we don't yet have pure hashtable library? There is imperative  
> hashtables, pretty complex as they need to rebuild entire table as  
> it grows. There is also simple assoc lists and tree/trie  
> implementations, but there is no simple non-modifiable hashes.

I know that Lennart had such a hashtable implementation as part of the  
hbcc source tree (so dating back to the late stream age or the very  
very early monad age), though I think it relied upon hbc's LazyArray.

One obvious way to make non-modifiable hash tables useful is to "eat  
your own tail" non-strictly--- aggregate a set of hash table entries,  
construct a hash table from them, and plumb the resulting hash table  
into the original computation by tying the knot.  This works really  
well if you can construct the bucket lists lazily and if you specify  
the table size up front.  You can't make this trick work at all for  
tree-based maps in general, because the structure of the tree depends  
upon all the keys inserted.  You also can't make this trick work if  
you base the size of the hash table on the number of keys inserted,  
maximum bucket load, etc.  Finally, it doesn't work with strict arrays  
at all.

So a nice niche for a small and clever static hash table.

-Jan