面向新手的 STArray 文档和状态/ST 相关问题

Question

我很难从文档和通过 Google 找到的其他操作/讨论中理解 STArray。下面我还有一些相关问题。

根据文档，STArray 是

ST monad 中的可变装箱和未装箱数组。

这给我的印象是，STArray 旨在用作在函数之间传递的状态（想象一下您有一个必须经常更新的向量）。

显然，这的用法有所不同：

ST s (STArray s a e)

这里的状态 s 是什么？如果是内部使用，那为什么不对用户隐藏呢？

这也意味着，如果我们想使用 STArray s Int Int 作为状态传递，则需要定义

type StateArray a = Control.Monad.State (ST s (STArray s Int Int)) a

这似乎相当麻烦。

最后，

• ST 和 State 之间有什么区别？
• 如果 ST 和 IO 供“内部”使用，那么 STArray 和 IOArray 之间有什么区别？

谢谢你！！

Answer 1

ST 是一个 monad，其中允许有限类型的副作用，即可变引用和可变数组。因此，它允许您实现从外部世界看来是纯粹的函数，但在内部使用突变。

这与 State 不同，后者仅通过将状态作为额外的输入和输出通过计算进行线程化来伪造突变。在实现一些命令式算法时，这种差异很重要，因为它们有时需要突变才能有效实现。例如，在 State 单子中使用常规数组，您只能通过制作副本来修改它，而使用 ST 您可以就地进行真正的突变。

之所以我们同时拥有ST和IO，是因为ST提供了比IO更强的保证，即：

1. ST 不允许任意副作用，例如访问文件系统。
2. 我们可以保证 ST does 允许的副作用无法逃脱 runST 的作用域，因此从外界来看它可以被视为纯粹的。

之所以能保证副作用无法逃逸，与类型变量s有关。由于任何 ST 操作在 s 中都必须是多态的，因此您无法编写允许任何可变引用进入或离开 runST 范围的代码，因为类型检查器会抱怨它不能保证您的操作的 s 与引用或数组的 s 相同，除非它们来自相同的 runST 作用域。

作为将 ST monad 与可变数组结合使用的示例，以下是埃拉托斯坦筛法的实现：

import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed

primesUpto :: Int -> [Int]
primesUpto n = [p | (p, True) <- assocs $ sieve n]

sieve :: Int -> UArray Int Bool
sieve n = runSTUArray $ do
    sieve <- newArray (2, n) True
    forM_ [2..n] $ \p -> do
        isPrime <- readArray sieve p
        when isPrime $ do
            forM_ [p*2, p*3 .. n] $ \k -> do
                writeArray sieve k False
    return sieve

_{runSTUArray 是 runST< 的特殊形式/code> 它允许您在冻结数组并将其作为不可变数组返回之前使用内部突变来构建数组。 newArray、readArray 和 writeArray 执行您所期望的操作。}

如您所见，sieve 的类型签名 表明它是一个纯函数，确实如此。然而，它在内部大量使用突变来有效地实现它。