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

我很难从文档和其他howtos /我通过谷歌发现的讨论了解STArray 。 下面还有一些相关的问题。

根据文件， STArray是

ST monad中的可变盒装和非盒装数组。

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

显然，这有不同的用法：

 ST s (STArray sae) 

这里的状态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中允许有限的副作用types，即可变引用和可变数组。 因此，它允许你实现从外部看到的纯粹的函数，但在内部使用突变。

这与State不同，它只是通过将计算作为额外的input和输出来穿越状态来进行突变。 当实施一些强制性algorithm时，差异是重要的，因为它们有时需要突变来有效地实施。 例如，在State monad中使用常规数组，只能通过复制来修改它，而使用ST可以在原地进行真正的变异。

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

1. ST不允许任意的副作用，例如访问文件系统。
2. 我们可以保证ST的副作用确实让人无法逃脱runST的范围，所以可以把它看作是纯粹的外部世界。

我们可以保证副作用不能逃避的原因与typesvariabless 。 由于任何ST动作都必须是多态s ，所以你不能编写允许任何可变引用进入或离开runST的范围的runST ，因为types检查器会抱怨说它不能保证你的动作和引用的动作或数组是相同的， 除非它们来自相同的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是runSTUArray的一种特殊forms，它可以让你在冻结数组之前使用内部runST来构build一个数组，并将它作为一个不可runST组返回。 newArray ， readArray和writeArray做你所期望的。}

正如你所看到的， sieve的types签名表明它是一个纯函数，而且是。 然而，它在内部大量使用突变来有效地实现它。