1

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)
Community
  • 1
  • 1
גלעד ברקן
  • 22,586
  • 3
  • 21
  • 58

1 Answers1

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
cdk
  • 6,626
  • 21
  • 50