[Haskell-cafe] mapping unfreeze over an IntMap of IOUArrays

[Bulat Ziganshin]

Hello Don,

Wednesday, November 12, 2008, 12:51:33 AM, you wrote:

>> btw, i made here some time ago proposal about pure hashtables

> Did you end up implementing this?

yes, i have published here all the 10 lines of implementation :)))

citing letter to you:

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)])

-- size is the size of array (we implent closed hash)
-- hash is the hash function (a->Int)
-- list is assoclist of items to put in hash
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)


example:

main = do let assoclist = [("one", 1), ("two", 2), ("three", 3)]
              hash = HT.create 10 Data.HashTable.hashString assoclist
          print (HT.lookup "one" hash)
          print (HT.lookup "zero" hash)



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