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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
