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

[R. Turk]

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... 
> 
> J.A.

I assume you're talking about something like this:

{-# OPTIONS -fglasgow-exts #-}
{- I want a Hashable instance for String ;) -}
import Data.FiniteMap
import Data.HashTable (hashInt, hashString)
import Data.Int (Int32)

class Hashable a where hash :: a -> Hash
instance Hashable Int where hash = hashInt
instance Hashable String where hash = hashString

type Hash = Int32
newtype HashTable a b = HT (FiniteMap Hash [b])

emptyHT     :: HashTable a b
emptyHT     = HT emptyFM

addToHT     :: (Hashable a) => HashTable a b -> a -> b ->
HashTable a b
addToHT (HT m) k v
            = HT $ addToFM_C (flip (++)) m (hash k) [v]

Of course one could do that, and it would be (expected) O(log n)
instead of O(n), but I doubt I'd really call it a hashtable...
It's more like a variant on (Python's?) Decorate-Sort-Undecorate
pattern. (Replacing a direct comparison by a conversion to
something else which can be compared.) However, it could still be
usefull if there will be lots of lookups and comparing elements
is expensive.

Groetjes,
Remi