[Haskell-cafe] Pure hashtable library

[Don Stewart]

bulat.ziganshin:
> Hello Richard,
> 
> Thursday, August 28, 2008, 5:28:46 AM, you wrote:
> 
> >>> trie: O(len)*O(width)
> >>> hashed trie: O(len)
> >>> hash: O(len)
> 
> > If "width" here refers to the branching factor of the trie,
> > it's actually O(len.lg(width)), and the width that matters
> > is not the *possible* number of choices but the *actual*
> > number.
> 
> i thought about using list to hold all variations at the trie node. with
> a (balanced) tree at each node we will have even more overheads
> 
> 
> > The great problem with hash tables is devising good hash
> > functions.  There is a vast literature about hash tables,
> > but there is very little about how to design good hash
> > functions for anything other than numbers and maybe strings.
> 
> 1. tries also work only for strings and other lists
> 2. i don't want to go into discussing well-known pluses and minuses of
> data structures. my point was just that we have great alternative to
> trees/tries which should be implemented many years ago. i've used a
> lots of assoclists in my program, sometimes this really degraded
> performance (although it's yet another question - why tree/trie
> structures doesn't provide simple List.lookup replacement function and
> why i'm so lazy to still not learning their APIs)
> 

Seems like you can make a pure hashtable by unsafePerformIO on the
impure one, and exporting only 'lookup'..

-- Don