1

但是，文档STT说：

这个单子转换器不应该与可以包含多个答案的单子一起使用，例如列表单子。原因是状态令牌将在不同的答案中重复，这会导致坏事发生（例如失去参考透明度）。安全单子包括单子 State、Reader、Writer、Maybe 以及它们相应的单子转换器的组合。

我希望能够自己判断对STTmonad 的某种使用是否安全。特别是，我想了解与 List monad 的交互。我知道那STT sloc (ListT (ST sglob)) a是不安全的，但是呢STT sloc []？

我发现（至少在 GHC 中）最终是使用,等STT神奇的构造实现的。是否有任何关于这些对象如何表现的准确文档？MuteVar#State#realWorld#

这与我之前的一个问题密切相关。

4

1 回答 1

4

您实际上并不需要了解如何State#实施。您只需将其视为通过计算线程传递的令牌，以确保操作的特定执行顺序，ST否则这些操作可能会被优化掉。

在STT s []monad 中，您可以将列表操作视为生成一棵可能的计算树，并在叶子上给出最终答案。在每个分支点，State#令牌都会被拆分。所以，粗略地说：

  • 在从根到叶的特定路径中，单个State#令牌贯穿整个路径，因此当需要答案时，所有 ST 操作将按顺序执行
  • 对于两条路径，它们共有的树部分中的 ST 操作（在拆分之前）是安全的，并且以您期望的方式在两条路径之间正确“共享”
  • 两条路径拆分后，两个独立分支中动作的相对顺序未指定

我相信还有一个进一步的保证，尽管这有点难以推理：

如果在最终的答案列表（即由 生成的列表runSTT）中，您在 index 处强制使用单个答案k- 或者，实际上，我认为如果您只是强制证明在 index 处有答案的列表构造函数k- 那么直到该答案的树的深度优先遍历中的所有动作都将被执行。问题是树中的其他操作也可能已执行。

例如，以下程序：

{-# OPTIONS_GHC -Wall #-}

import Control.Monad.Trans
import Control.Monad.ST.Trans

type M s = STT s []

foo :: STRef s Int -> M s Int
foo r = do
  _ <- lift [1::Int,2,3]
  writeSTRef r 1
  n1 <- readSTRef r
  n2 <- readSTRef r
  let f = n1 + n2*2
  writeSTRef r f
  return f

main :: IO ()
main = print $ runSTT $ foo =<< newSTRef 9999

-O0当使用(answer is [3,3,3]) 与-O2(answer is )编译时，在 GHC 8.4.3 下会产生不同的答案[3,7,15]。

在其（简单）计算树中：

    root
   /  |  \
  1   2   3          _ <- lift [1,2,3]
 /    |    \
wr    wr    wr       writeSTRef r 1
|     |     |
rd    rd    rd       n1 <- readSTRef r
|     |     |
rd    rd    rd       n2 <- readSTRef r
|     |     |
wr    wr    wr       writeSTRef r (n1 + n2*2)
|     |     |
f     f     f        return (n1 + n2*2)

我们可以推断，当需要第一个值时，左分支中的写/读/读/写动作已经执行。（在这种情况下，我认为中间分支上的写入和读取也已执行，如下所述，但我有点不确定。）

当求第二个值时，我们知道左分支的所有动作都已按顺序执行，中间分支的所有动作都按顺序执行，但我们不知道这些分支之间的相对顺序。它们可能已经完全按顺序执行（给出答案3），或者它们可能已经交错，以使左分支上的最终写入落在右分支上的两次读取之间（给出答案1 + 2*3 = 7.

于 2018-08-31T17:01:39.883 回答