Haskell: map runST

Question

I have a binding for a type [ST s (Int, [Int])] and I am trying to apply runST to each element using map as follows:

name :: [ST s (Int, [Int])] --Of Course there is a real value here
map runST name

This gives me an error message

Couldn't match expected type `forall s. ST s b0'
    with actual type `ST s0 (Int, [Int])'
Expected type: [forall s. ST s b0]
  Actual type: [ST s0 (Int, [Int])]
In the second argument of `map', namely `name'
In the expression: map runST name

There must be something I am misunderstanding. I am aware of runST and function composition, but am unsure if this applies.

Thanks for everyones time!

Answer 1

Each time you run a state transformer with runST, it operates on some local state that is separate from all other state transformers. runST creates a new state type and calls its argument with that type. So, for example, if you execute

let x = runST (return ())
    y = runST (return ())
in (x, y)

then the first return () and second return () will have different types: ST s1 () and ST s2 (), for some unknown types s1 and s2 that are created by runST.

You are trying to call runST with an argument that has state type s. That is not the state type that runST creates, nor is any other type you can choose. To call runST, you must pass an argument that can have any state type. Here is an example:

r1 :: forall s. ST s ()
r1 = return ()

Because r1 is polymorphic, its state can have any type, including whatever type is selected by runST. You can map runST over a list of polymorphic r1s (with -XImpredicativeTypes):

map runST ([r1, r1] :: [forall t. ST t ()])

However, you cannot map runST over a list of non-polymorphic r1s.

map runST ([r1, r1] :: forall t. [ST t ()]) -- Not polymorphic enough

The type forall t. [ST t ()] says that all list elements have state type t. But they need to all have independent state types because runST is called on each one. That is what the error message means.

If it is okay to give the same state to all list elements, then you can call runST once as shown below. The explicit type signature is not required.

runST (sequence ([r1, r1] :: forall t. [ST t ()]))