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⑈