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

R. Turk rturk at science.uva.nl
Wed Nov 10 05:34:32 EST 2004

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.


More information about the Haskell-Cafe mailing list