[Haskell-cafe] FiniteMap-like module for unordered keys?
GK at ninebynine.org
Thu Nov 11 05:33:24 EST 2004
At 16:13 10/11/04 -0800, John Meacham wrote:
> > ... (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
>it is immutable you can choose things like the number of buckets more
Indeed. In a past life, I implemented an IP address translation system
where a key requirement was that performance would not degrade as the
number of active addresses increased. Performance being very dominated by
lookups. The solution adapted an hash table scheme with O(1) lookup
characteristics. Insertion/deletion costs were sub O(N), but with a very
high constant factor.
(The main problem was complexity: the lookup table was a pig to debug!)
More information about the Haskell-Cafe