STArray documentation for newbies and State/ST related questions

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.

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.

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

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.

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.

As an example of using the ST monad with mutable arrays, here is an implementation of the Sieve of Erathostenes:

import Control.Monadimport Control.Monad.STimport Data.Array.STimport Data.Array.UnboxedprimesUpto :: Int -> [Int]primesUpto n = [p | (p, True) <- assocs $ sieve n]sieve :: Int -> UArray Int Boolsieve 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 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.