haskell - 修改 ST Monad 中的哈希表

Question

所以，我一直在寻找可变哈希表(出于速度原因)，以及 updated answer唐·斯图尔特 (Don Stewart) 带领我尝试了 hashtables .

由于对 ST Monad 有点缺乏经验，我成功扩展了 given example到:

{-# 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绑定(bind)，而不是 <- .

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

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

它给出了以下错误(以及其他错误):哈希表.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 版本？

Answer 1

您是正确的，一旦哈希表离开 ST monad，您就不能对其进行操作。答案不是进行 toList/fromList 编码(marshal)处理，而是只使用一个 runST 来覆盖 一切 你需要用变异做的事情那张 table 。

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