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

[Graham Klyne]

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 
>you know
>it is immutable you can choose things like the number of buckets more
>inteligently.

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

#g


------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact