初级可变Haskell哈希表

Question

尝试使用简单的哈希表算法,似乎对我使用Data.HashMap.我希望更好地理解如何实现一个可变的哈希表(这将是Data.HashTable.IO？),以便提高性能.我完全迷失了...试图修改这里的例子,但是找不到我通过我获得的IO类型的方式(双关语)...提前感谢任何类型的漫游或参考一个.

例如,如何使用可变哈希表实现这个简单的练习？

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)

Answer 1

类型签名HM.insert是

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

从这个签名我们可以看到,insert没有返回插入元素的新hashmap,它实际上是一个IO为我们插入的动作,在适当的位置改变旧的hashmap.

同样,也会HM.lookup在IOmonad中返回结果:

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

所以我们需要做一些工作来绑定IO这些函数返回的动作.我想你想要这样的东西.

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