Elementary Mutable Haskell Hash Table

Question

Experimenting with a simple hash table algorithm, seemed to work for me using Data.HashMap. I am hoping to understand better how to implement a mutable hash table (would this be Data.HashTable.IO?) that would allow for faster performance. I am totally lost...tried to modify the example here but could not find my way through the IO types I got in return (pun intended)...thanks in advance for any kind walk-through or reference to one.

For example, how to implement this simple exercise using a mutable hash table?

import qualified Data.HashMap as HM (toList,lookup,insert,empty)

f list = g list HM.empty where
  g []     h = HM.toList h
  g (x:xs) h = case HM.lookup (x-1) h of
                 Just _  -> g xs (HM.insert x (x + 1) h)
                 Nothing -> g xs (HM.insert x x h)

cdk · Accepted Answer · 2013-07-12T23:31:53.553

6

The type signature for HM.insert is

insert :: IOHashTable h k v -> k -> v -> IO ()

From this signature we can see that insert doesn't return a new hashmap with the element inserted, it is actually an IO action that does the inserting for us, mutating the old hashmap in place.

Similarly, HM.lookup returns its result in the IO monad too:

lookup :: IOHashTable h k v -> k -> IO (Maybe v)

So we'll need to do some work binding the IO actions these functions return. I think you want something like this.

f xs = g xs HM.empty
    where g [] h     = HM.toList h
          g (x:xs) h = do
              res <- HM.lookup (x-1) h
              case res of
                  Nothing -> HM.insert h x x
                  Just _  -> HM.insert h x (x+1)
              g xs h

edited Jul 12 '13 at 23:31

answered Jul 12 '13 at 18:56

cdk

6,698
24
51

Thanks! That got me passed the case/lookup hurdle (...there seem to be a few more things to workout, though, like `new` rather than `empty`...and how to show IO types, like `IO [(k0, v0)]`, which is the result of `toList`?) – גלעד ברקן Jul 12 '13 at 19:26
2

if you have a `x :: IO a`, you can use `x >>= print` to show it – cdk Jul 12 '13 at 19:40
@groovy which is, by the way, merely a more expressive way of saying `\list <- x; print list` – Justin L. Jul 13 '13 at 09:47
@JustinL. you mean `do { a <- x; print a }`? Hopefully thats not some lambda syntax language extension I'm unaware of. – cdk Jul 13 '13 at 14:48
@ChrisDueck yes I do, not sure how that slash crept in there heh – Justin L. Jul 13 '13 at 16:24

Elementary Mutable Haskell Hash Table

1 Answers1