Data.HashTable

[Jan-Willem Maessen]

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

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

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries