3

所以，我一直在寻找可变哈希表（出于速度原因），Don Stewart 的更新答案让我尝试了hashtables。

由于对 ST Monad 有点缺乏经验，我成功地将给定的示例扩展为：

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE FlexibleContexts #-}

import qualified Data.HashTable.ST.Cuckoo as C
import qualified Data.HashTable.Class as H
import Control.Monad.ST.Safe
import Data.Text

type HashTable s k v = C.HashTable s k v

foo :: ST s (HashTable s Text Int)
foo = do
  ht <- H.newSized 1
  H.insert ht "abc" 1
  H.insert ht "dea" 3
  return ht

add1 :: HashTable s Text Int -> ST s (HashTable s Text Int)
add1 ht = do
  H.insert ht "abc" 2
  H.insert ht "dea" 4
  return ht

main = do
  let x = runST $ H.toList =<< foo
  print x
  let y = runST $ H.toList =<< add1 =<< foo
  print y

根据我的（有限的）理解，它允许以可变的方式对数据结构进行操作，但随后“冻结它们”并以可以逃脱的方式呈现结果runST- 因此我们可以使用let绑定，并且不是<-。

但是，我没有看到如何在不总是将其转换为列表的情况下对哈希表进行操作。以下代码甚至无法编译：

   -- does not compile
   let z = runST foo
   let w = runST $ add1 z
   print w

它给出了以下错误（除其他外）：hashtable.hs:31:19：

Couldn't match type `a' with `C.HashTable s Text Int'
  `a' is a rigid type variable bound by
      the inferred type of z :: a at hashtable01.hs:31:7
Expected type: ST s a
  Actual type: ST s (HashTable s Text Int)
In the second argument of `($)', namely `foo'
In the expression: runST $ foo
In an equation for `z': z = runST $ foo

这可能是由于s类型的限制，我的猜测是它可能正是出于这个原因。如果我们稍后使用z它，它不会有相同的值，因为它add1是在原地操作的，因此它不会是纯的。这个对吗？

但是，在这种特殊情况下，ST Monad 仅适用于以下情况：

  • 你给一个固定的输入
  • 您使用可变数据结构根据它计算新值
  • 您冻结结果，使其再次不可变。

任何进一步的更改都需要一个 toList/fromList 有效地复制值并保持原始不可变。当我写这篇文章时，我在想 - 呃，这是一个纯函数的定义，在 haskell 中随处使用，因此是 ST Monad 的用例（我是否达到了 ST 的启蒙？）

所以，我想在这种情况下真正的问题是：这个 toList/fromList 操作是不是很昂贵（2xO(n)），难道没有其他方法可以在没有 toList/fromList 函数对的情况下对副本进行操作吗？ . 还是我过于复杂了，我应该只使用 Hashtables 的 IO 版本？

4

1 回答 1

0

你是对的，一旦散列表离开ST单子，你就不能对它进行操作。答案不是进行toList/fromList封送处理，而是只使用一个单一runST的范围来覆盖您需要对表进行变异的所有内容。

即，正如 Louis 在评论中所写：“将所有其他内容拉入 ST monad，直到您拥有一个使用哈希表作为内部实现细节并且不将其暴露给其余代码的函数”。

于 2015-04-06T17:40:39.633 回答