STArray文档新手和国家/ ST相关的问题 [英] STArray documentation for newbies and State/ST related questions

问题描述

我也很难从我已经通过谷歌找到的文档和HOWTO文档/讨论理解 STArray 。我有下面的一些相关问题。

I have a hard time to understand STArray from the documentation and other howtos/discussion I've found through Google. I've got some more related questions below.

根据该文件， STArray 是

在ST单子可变装箱和取消装箱阵列。

Mutable boxed and unboxed arrays in the ST monad.

这给我的IM pression，即 STArray ，就是要作为的状态的正在传递函数之间的（想象一下你有一个必须经常更新的向量）。

This gave me the impression, that STArray is meant to be used as a state being passed around between functions (imagine you have a vector that has to be updated often).

显然，这是用来虽然不同：

Apparently this is used differently though:

ST s (STArray s a e)

什么是国家取值在这里？如果是内部使用，那么为什么这难道不是对用户隐藏？

What is the state s here? If it is used internally, then why is this not hidden from the user?

这也意味着，如果我们要使用 STArray小号诠释诠释正在传递的状态，一会定义

This also means, if we want to use a STArray s Int Int being passed around as state, one would define

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

这似乎是相当麻烦的。

which seems rather cumbersome.

最后，

• 是 ST的区别和国家？


• 是 STArray 和 IOArray ，如果 ST 和 IO 都是为了内部使用？



• what is the difference between ST and State?
• what is the difference between STArray and IOArray, if the ST and IO are meant for "internal" use?

感谢您!!

推荐答案

ST 是在其中的副作用有限的类型是允许一个单子，也就是可变引用和可变阵列。因此，它可以让你实现这是从外界看到的纯函数，但是在内部使用该突变。

ST is a monad in which a limited type of side effects are allowed, namely mutable references and mutable arrays. Thus it allows you to implement functions which are pure as seen from the outside world, but which use mutation internally.

这是从国家，它只能通过你的计算作为额外的输入和输出线程状态假货突变不同。实施一些势在必行算法时，因为它们有时需要突变被有效地实施的差别是重要的。例如使用在国家单子定期阵列，则只能通过复印，而用 ST 修改你可以就地真正的突变。

This is different from State, which only fakes mutation by threading the state through your computation as extra inputs and outputs. The difference is important when implementing some imperative algorithms, because they sometimes need mutation to be implemented efficiently. For example using a regular array in a State monad, you can only modify it by making a copy, whereas with ST you can have true mutation in-place.

我们之所以兼得 ST 和 IO 是 ST 提供了更强的保障比 IO ，即：

The reason why we have both ST and IO is that ST provides stronger guarantees than IO, namely:

1. ST 不允许随意副作用，例如像访问文件系统。


2. 我们可以保证的副作用 ST 的确实的允许不能逃脱的范围 runST ，因此它可以被看作是从外界纯

1. ST does not allow arbitrary side effects like for example accessing the file system.
2. We can guarantee that the side effects ST does allow cannot escape the scope of runST, and so it can be seen as pure from the outside world.

为什么我们可以保证，副作用无法逃避的原因是相关的类型变量取值。由于任何ST行动都必须在取值是多态的，你可以不写code，它允许任何可变引用进入或离开 runST范围，因为类型检查器会抱怨它不能保证的您的行动，并引用或数组的是相同的除非的他们都来自同一个 runST 范围。

The reason why we can guarantee that the side effects cannot escape is related to the type variable s. Since any ST action must be polymorphic in s, you cannot write code which allows any mutable references to enter or leave the scope of a runST, because the type checker will complain that it cannot guarantee that the s of your action and that of the reference or array are the same unless they come from the same runST scope.

由于使用 ST 单子带可变数组，这里是Erathostenes的筛的实现的例子：

As an example of using the ST monad with mutable arrays, here is an implementation of the Sieve of 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 你会期待什么

_{runSTUArray is a specialized form of runST which allows you to build an array using mutation on the inside, before freezing it and returning it as an immutable array. newArray, readArray and writeArray do what you'd expect.}

正如你所看到的，筛的类型签名表明它是一个纯函数，它是。然而，它使用大量的突变在里面能够有效地实现它。

As you can see, the type signature of sieve indicates that it's a pure function, and it is. However, it uses mutation heavily on the inside to implement it efficiently.

这篇关于STArray文档新手和国家/ ST相关的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！