[Haskell-cafe] Pure hashtable library

[Jules Bean]

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 

No.

"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.

Jules