[Haskell-cafe] Pure hashtable library

Bulat Ziganshin bulat.ziganshin at gmail.com
Thu Aug 28 02:56:24 EDT 2008

Hello Don,

Thursday, August 28, 2008, 10:32:43 AM, you wrote:

> Seems like you can make a pure hashtable by unsafePerformIO on the
> impure one, and exporting only 'lookup'..

probably yes, but it will lose a bit of performance due to incremental
building of hashtable. actually, writing HT module from scratch is
very easy - all we need is a prime searching function (in order to
establish array size). everything else:

data HT a b = HT (a->Int) (Array Int [(a,b)])

create size hash list = HT hashfunc
                           (accumArray (flip (:))
                                       (0, arrsize-1)
                                       (map (\(a,b) -> (hashfunc a,b)) list)

  where arrsize     =  head$ filter (>size)$ iterate (\x->3*x+1) 1
        hashfunc a  =  hash a `mod` arrsize

lookup a (HT hash arr) = List.lookup a (arr!hash a)

Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com

More information about the Haskell-Cafe mailing list