[Haskell-cafe] can there be (hash-table using) O(n) version of this (I think currently) n log n algo?

Matthias Görgens matthias.goergens at googlemail.com
Sat Jul 18 05:50:32 EDT 2009

However you can use the wider idea of hashing: A nesting of two finite
maps.  One fast, but approximative map.  And one slow, but exact map.
The quintessential example is an array indexed with some hash function
for the first map.  And linked lists of (key,value) pairs as the

In Haskell you might want to use IntMap and a the mentioned list of
pairs (combined with the lookup functions from Data.List).  Of course
you need to supply a function to hash your keys to Int for the IntMap.

More information about the Haskell-Cafe mailing list