map runSTArray over a list of STArrays?

Question

I have a function that creates recursively a flattened list of matrices from a tree that have to be mutable as their elements are updated often during their creation. So far I have come up with a recursive solution that has the signature:

doAll :: .. -> [ST s (STArray s (Int, Int) Int)]

The reason I do not return the [UArray (Int,Int) Int] directly is because doAll is called recursively, modifies elements of the matrices in the list and appends new matrices. I don't want to freeze and thaw the matrices unnecessarily.

So far so good. I can inspect the n-th matrix (of type Array (Int, Int) Int) in ghci

runSTArray (matrices !! 0)
runSTArray (matrices !! 1)

and indeed I get the correct results for my algorithm. However, I didn't find a way to map runSTUArray over the list that is returned by doAll:

map (runSTArray) matrices

Couldn't match expected type `forall s. ST s (STArray s i0 e0)'
            with actual type `ST s0 (STArray s0 (Int, Int) Int)'

The same problem happens if I try to evaluate recursively over the list or try to evaluate single elements wrapped in a function

Could someone please explain what is going on (I didn't really understand the implications of the forall keyword) and how I could evaluate the arrays in the list?

Answer 1

This is an unfortunate consequence of the type trick that makes ST safe. First, you need to know how ST works. The only way to get from the ST monad to pure code is with the runST function, or other functions built upon it like runSTArray. These are all of the form forall s.. This means that, in order to construct an Array from an STArray, the compiler must be able to determine that it can substitute any type it likes in for the s type variable inside runST.

Now consider the function map :: (a -> b) -> [a] -> [b]. This shows that every element in the list must have exactly the same type (a), and therefore also the same s. But this extra constraint violates the type of runSTArray, which declares that the compiler must be able to freely substitute other values for s.

You can work around this by defining a new function to first freeze the arrays inside the ST monad, then run the resulting ST action:

runSTArrays :: Ix ix => (forall s. [ST s (STArray s ix a)]) -> [Array ix a]
runSTArrays arrayList = runST $ (sequence arrayList >>= mapM freeze)

Note the forall requires the RankNTypes extension.

Answer 2

You just bounced against the limitations of the type system.

The runSTArray has a higher ranked type. You must pass it a ST-action whose state type variable is unique. Yet, in Haskell it is normally not possible to have such values in lists.

The whole thing is a clever scheme to make sure that values you produce in an ST action can't escape from there. Which means, it looks like your design is somehow broken.

One suggestion: can't you process the values in another ST action, like

sequence [ ... your ST s (STArray s x) ...] >>= processing
  where
     processing :: [STArray s x] -> ST s (your results)