[Haskell-cafe] Pure hashtable library

[Bulat Ziganshin]

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