Data.HashTable
Sebastian Sylvan
sebastian.sylvan at gmail.com
Thu Mar 6 17:16:22 EST 2008
On Thu, Mar 6, 2008 at 9:48 PM, Neil Mitchell <ndmitchell at gmail.com> 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.html
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.).
--
Sebastian Sylvan
+44(0)7857-300802
UIN: 44640862
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20080306/4c8dc1b8/attachment.htm
More information about the Libraries
mailing list