新手和州/ ST相关问题的STArray文档

Question

我很难STArray通过Google找到的文档和其他howtos /讨论来理解.我在下面有一些更相关的问题.

根据文档,STArrays是

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？
• 什么是STArray和IOArray,如果ST和IO是否意味着"内部"使用？

谢谢!!

Answer 1

ST是一种monad,其中允许有限类型的副作用,即可变引用和可变阵列.因此,它允许您实现从外部世界看到的纯函数,但在内部使用变异.

这是不同的State,它只通过将计算状态作为额外的输入和输出线程化来伪造突变.在实现一些命令性算法时,差异很重要,因为它们有时需要突变才能有效实施.例如,在Statemonad中使用常规数组,您只能通过复制来修改它,而ST您可以在原地进行真正的突变.

为什么我们有两个原因ST,并IO是ST提供比更强的保证IO,即:

1. ST 不允许任意副作用,例如访问文件系统.
2. 我们可以保证副作用ST 确实让人无法逃避范围runST,因此它可以被视为来自外界的纯粹.

我们可以保证副作用无法逃脱的原因与类型变量有关s.由于任何ST动作必须是多态的s,你不能编写允许任何可变引用进入或离开a范围的代码runST,因为类型检查器会抱怨它不能保证s你的动作和引用或数组的动作是同样的,除非他们来自同一个runST范围.

作为使用ST具有可变数组的monad 的示例,这里是Erathostenes筛选的实现:

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表示它是纯函数,它是.但是,它在内部使用突变来有效地实现它.