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

Question

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

根据文档，STArray 是

Mutable boxed and unboxed arrays in the 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 单子(monad)中使用常规数组，您只能通过制作副本来修改它，而使用 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 的一种特殊形式，它允许您在卡住数组并将其作为不可变数组返回之前使用内部突变来构建数组。 newArray、readArray 和 writeArray 执行您所期望的操作。}

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