1

使用 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)
4

1 回答 1

6

的类型签名HM.insert是

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

从这个签名中我们可以看到，insert它不会返回插入元素的新哈希图，它实际上是一个IO为我们插入的动作，改变了旧的哈希图。

同样，在monad 中也HM.lookup返回其结果：IO

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
于 2013-07-12T18:56:52.237 回答