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
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
