STArray documentation for beginners and state / ST related issues

Question

I find it difficult to understand STArray from the documentation and other activities / discussions that I found through Google. I have a few more related questions.

According to the documentation, STArray

Mutable boxed and unboxed arrays in ST monad.

It seemed to me that STArray supposed to be used as a state passed between functions (imagine that you have a vector that needs to be updated frequently).

This seems to be used in different ways:

 ST s (STArray sae) 

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

It also means that if we want to use STArray s Int Int , passed as a state, we could define

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

which seems pretty bulky.

Finally,

• What is the difference between ST and State ?
• What is the difference between STArray and IOArray if ST and IO are intended to be used internally?

Thank!

Answer 1

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

This differs from State in that it only fakes a mutation by streaming state through your calculations as additional inputs and outputs. The difference is important when implementing some imperative algorithms, because sometimes it is required that the mutation be effectively implemented. For example, using a regular array in the State monad, you can only change it by creating a copy, whereas with ST you can have a true mutation in place.

The reason we have ST and IO is because ST provides higher guarantees than IO , namely:

• ST does not allow arbitrary side effects, for example, access to the file system.
• We can guarantee that the side effects of ST really do not avoid the runST volume, and therefore it can be considered as pure from the outside world.

The reason we can guarantee that side effects cannot go away is because of a variable of type s . Since any ST action must be polymorphic in s , you cannot write code that allows any mutable links to enter or leave the runST area, as the type checker will complain that it cannot guarantee that s your action and link value or arrays are the same if they do not belong to the same region of runST .

An example of using the ST monad with variable arrays is the implementation of the eratosten sieve:

 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 is a specialized form of runST that allows you to build an array using the mutation inside before freezing it and returning it as an immutable array. newArray , readArray and writeArray do what you expect.}

As you can see, a signature like sieve indicates that it is a pure function, and it is. However, he actively uses the mutation inside to effectively implement it.