[Haskell-cafe] FiniteMap-like module for unordered keys?

[John Meacham]

On Tue, Nov 09, 2004 at 11:41:49PM +0000, Jorge Adriano Aires wrote:
> Hello, 
> 
> > A hash-table becomes rather useless without mutable state AFAICS.
> > Without it, one might almost just as well use a list of pairs...
> 
> Could you please elaborate? Is there motive why an Hash Table, implemented as 
> FiniteMap of Lists, for instance, wouldn't be worth to using over a simple 
> List? (This wouldn't help G. Klyne of course). I've always wondered why a 
> non-monadic version of is not provided in the GHC libs... 

Sometimes you are willing to pay an arbitrary setup cost for very fast
future lookups. for things like symbols tables for instance. This is
where a constant non-monadic hash would be quite useful, especially since you know
it is immutable you can choose things like the number of buckets more
inteligently. or if you wanted to go crazy, generate a perfect-hash on
the fly. Binary trees are good at a lot of things, but their memory
locality is pretty cruddy for lookups or when your key comparason
operator is slow. (I am aware of the absurdity of thinking about memory
locality with a dynamic-dispatch STG-machine, but old habits from my
Kernel programming days die hard :) )
        John

-- 
John Meacham - ⑆repetae.net⑆john⑈