修改ST Monad中的哈希表 [英] Modify Hashtables in the ST Monad

问题描述

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

在ST Monad方面有点缺乏经验，我成功扩展了举例：

  { - ＃LANGUAGE OverloadedStrings＃ - } 
 { - ＃LANGUAGE ScopedTypeVariables＃ - } 
 { - ＃LANGUAGE FlexibleContexts＃ - } 
 
将合格的Data.HashTable.ST.Cuckoo导入为C 
导入合格的Data.HashTable.Class作为H 
导入Control.Monad.ST.Safe 
导入Data.Text 
 
类型HashTable skv = C.HashTable skv 
 
 foo :: ST s（HashTable s Text Int）
 foo = do 
 ht < - H.newSized 1 
 H.insert htabc1 
 H.insert htdea3 
 return ht 
 
 add1 :: HashTable s Text Int  - > ST s（HashTable s Text Int）
 add1 ht = do 
 H.insert htabc2 
 H.insert htdea4 
 return ht 
 
 main = do 
 let x = runST $ H.toList =<< foo 
 print x 
 let y = runST $ H.toList =<< add1 =<< foo 
 print y 
  

从我的（有限）理解中，它允许对数据结构进行操作一个可变的方式，但是然后'冻结它们'并以可通过 runST 逃脱的方式呈现结果，因此我们可以使用 let 绑定，而不是< - 。

然而，我没有看到我可以如何在散列表上运行，而无需总是将它转换为列表。下面的代码甚至没有编译：

   - 不能编译
 let z = runST foo 
让w = runST $ add1 z 
 print w 
  

它给出了以下错误）：
hashtable.hs：31：19：

 不能与`C'类型匹配。 HashTable s Text Int'
'a'是一个刚性类型变量，由
绑定，在hashtable01.hs中为z :: a的推断类型：31：7 
期望类型：ST sa 
实际类型：ST s（HashTable s Text Int）
在'（$）'的第二个参数中，即'foo'
在表达式中：runST $ foo 
在等式对于`z'：z = runST $ foo 
  

这可能是由于 s 约束在类型中，我的猜测是它可能正是出于这个原因。如果我们稍后使用 z ，它将不会具有相同的值，因为 add1 已就位，因此它不会是纯粹的。这是正确的吗？

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

• 您给出一个固定的输入


• 您可以使用可变数据结构计算新值冻结结果，使其再次变得不可变。

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

因此，我猜这个例子中真正的问题是：是不是这个toList / fromList操作昂贵（2xO（n）），并且不能有另一种方法来操作没有toList / fromList函数对的副本。或者我过于复杂了，我应该只使用Hashtables的IO版本？ 解决方案

你是正确的，你不能操作在散列表离开 ST monad时，答案不是做 toList / fromList 封送，而是只有一个 runST 的范围超过你需要做的就是改变表格。

Ie正如路易斯在评论中所写的：把所有其他东西都放到ST monad中，直到你有一个使用哈希表作为内部实现细节的函数，并且不会将其暴露给代码的其余部分。

So, I was looking for mutable hashtables (for speed reasons), and the updated answer from Don Stewart led me to try out hashtables.

Being a bit inexperienced in the ST Monad, I successfully expanded the given example to:

{-# 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

From my (limited) understanding it allows to operate on data structures in a mutable way, but then 'freeze them' and present the result in such a way that it can be escaped from, through runST - and thus we can use the let bindings, and not <-.

However, I was failing to see how I could operate on an hashtable without always converting it to/from lists. The following code does not even compile:

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

It gives the following error (among others): 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

This is probably due to the s constrain in the type, and my guess is that it's probably there for precisely that reason. If we would later use z it would not have the same value, since the add1 operated in place, and thus it would not be pure. Is this correct?

But then, the ST Monad in this particular case is only useful for a situation where:

• You give a fixed input
• You calculate the new value based on it, using mutable data structures
• You freeze the result, making it imutable again.

Any further change requires a toList/fromList that efectively copies the values and keeps the original imutable. As I am writing this, I'm thinking - duh, this is the definition of a pure function, as used everywhere in haskell, and thus the use case for the ST Monad (have I reached ST enlightenment?)

So, i guess the real question in this case is: isn't this toList/fromList operation expensive (2xO(n)), and couldn't it there be another way to operate on a copy without the toList/fromList pair of functions. Or am I overcomplicating, and I should just use the IO version of Hashtables?

解决方案

You are correct that you can't operate on a hashtable once it leaves the ST monad. The answer is not to do toList/fromList marshaling, but instead to just have a single runST that scopes over everything you need to do with mutating that table.

I.e. as Louis wrote in the comments: "pull everything else into the ST monad until you have a function which uses a hash table as an internal implementation detail and doesn't expose that to the rest of the code".

这篇关于修改ST Monad中的哈希表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！