[Haskell-cafe] Pure hashtable library

Jules Bean jules at jellybean.co.uk
Wed Aug 27 11:59:55 EDT 2008

Bulat Ziganshin wrote:
> Hello Jules,
> Wednesday, August 27, 2008, 7:21:46 PM, you wrote:
>>> given these constraints, it should be just a 10-20 lines of code, and provide much better efficiency than any tree/trie implementations
>> Prove it.
>> To get "much better efficient" than a trie, the hash function has to be
>> so fast that it is faster than following (log n) pointers
> afaiu, trie search follows n pointers 


"n" is the number of strings in my data set (dictionary).

If I have "n" strings the average string length is asymptotically, in 
some sense, "log n". Of course for particular data sets it's may be more .

But "log n" is the length of the shortest unique coding, it's also the 
number of characters you typically need to traverse before you have 
reached a unique prefix, at which point your trie can short-circuit.

I appreciate that I didn't define my terminology ;) You might have a 
different "n".

I repeat my challenge "Prove it". I will be interested to see how much a 
good immutable hash outperforms Data.Map.

I would then also be interested to see how much it outperforms a decent 
Data.Map (such as your own AVL one) and a decent trie.


More information about the Haskell-Cafe mailing list