Re: Data.HashTable

On Mar 6, 2008, at 5:16 PM, Sebastian Sylvan wrote:

On Thu, Mar 6, 2008 at 9:48 PM, Neil Mitchell wrote: Hi

...

I learned at school, and I teach my students, * balanced binary tree: costs are log(size) * hashtable: cost are essentially constant

All true, but log(1000) = 10 [nitpick, its nearly always log base 2, not base 10]. 10 ~= constant.

...

... but indeed some experiments with Data.Map and Data.Hashtable support the point you made. That's either good for Data.Map or bad for Data.Hashtable.

I think both of those are true. Hashtable isn't a natural functional data structure, so is ignored, so is not improved. I suspect a Trie would be a much better data structure for most of the uses of Hashtable, but alas there is not one in the standard libraries.

How about this one? http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-IntMap...

You can use that to build a purely functional hash table quite easily I suspect (giving you worst case constant time lookup, and no fixed size nonsense, or re-hashing etc.).

Indeed, during my last go-round on Data.HashTable I used an IntMap to verify several different implementations. But I only ended up putting back some small changes to hashing due to lack of time. -Jan-Willem Maessen

-- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries