ST's use of RankNTypes to make its interface pure [duplicate]

Question

Given the following signature for running the monad ST

runST :: (forall s. ST s a) -> a

and the functions

newVar  :: a -> ST s (MutVar s a) 
readVar :: MutVar s a -> ST s a

Then the Haskell compiler will reject the following ill-typed expression

let v = runST (newVar True)
in runST (readVar v)

Because in order to evaluate runST, it's required that the type

readVar v :: ST s Bool 

must be generalized to

∀s . ST s Bool 

My question is then that the only job of the Universal quantifier here, is to ensure that the type variable s is always free in the context of evaluation avoiding generalization, am I right? or is there more about the universal quantifier here?

Answer 1

Let's read the type of runST. I added an explicit quatifier for a as well.

runST :: forall a . (forall s. ST s a) -> a

It reads as the following contract:

1. the caller chooses a fixed type a
2. the caller provides an argument x
3. the argument x must be of type ST s a for any choice of s. In other words, s will be chosen by runST, not by the caller.

Let's see a similar example:

runFoo :: forall a . (forall s. s -> [(s,a)]) -> [a]
runFoo x =
    let part1 = x "hello!"          -- here s is String
        -- part1 has type [(String, a)]
        part2 = x 'a'               -- here s is Char
        -- part2 has type [(Char, a)]
        part3 = x (map snd part2)   -- here s is [a]   (!!!)
        -- part3 has type [([a],a)]
    in map snd part1 ++ map snd part2 ++ map snd part3

test1 :: [Int]
test1 = runFoo (\y -> [(y,2),(y,5)])   -- here a is Int

test2 :: [Int]
test2 = runFoo (\y -> [("abc" ++ y,2)])       -- ** error
-- I can't choose y :: String, runFoo will choose that type!

Above, note that a is fixed (to Int), and that I can't put any restrictions on the type of y. Moreover:

test3 = runFoo (\y -> [(y,y)])    -- ** error

Here I am not fixing a in advance, but I'm trying to choose a=s. I am not allowed to do that: runFoo is allowed to choose s in terms of a (see part3 above), so a must be fixed in advance.

Now, to your example. The problem lies in

runST (newSTRef ...)

Here, newSTRef returns a ST s (STRef s Int), so it's trying to choose a = STRef s Int. Since a depends on s, this choice is invalid.

This "trick" is used by the ST monad to prevent references to "escape" from the monad. That is, it is guaranteed that after runST returns, all the references are now no longer accessible (and potentially they can be garbage collected). Because of this, the mutable state which was used during the ST computation has been thrown away, and the result of runST is indeed a pure value. This is, after all, the main purpose of the ST monad: it is meant to allow (temporary) mutable state to be used in a pure computation.

Answer 2

I think you're missing something. The actual message GHCi gives is:

Prelude> :m +Control.Monad.ST
Prelude Control.Monad.ST> data MutVar s a = MutVar
Prelude Control.Monad.ST> :set -XRankNTypes
Prelude Control.Monad.ST> data MutVar s a = MutVar
Prelude Control.Monad.ST> let readVar = undefined :: MutVar s a -> ST s a
Prelude Control.Monad.ST> let newVar = undefined :: a -> ST s (MutVar s a)
Prelude Control.Monad.ST> runST $ readVar $ runST $ newVar True

<interactive>:14:27:
    Couldn't match type ‘s’ with ‘s1’
    ‘s’ is a rigid type variable bound by
        a type expected by the context: ST s Bool at <interactive>:14:1
    ‘s1’ is a rigid type variable bound by
        a type expected by the context: ST s1 (MutVar s Bool)
        at <interactive>:14:19
    Expected type: ST s1 (MutVar s Bool)
    Actual type: ST s1 (MutVar s1 Bool)
    In the second argument of ‘($)’, namely ‘newVar True’
    In the second argument of ‘($)’, namely ‘runST $ newVar True’

The Haskell compiler rejects it not because of anything to do with readVar but rather because of a problem with newVar, which is that ST s (MutVar s a) allows the s to "escape" its context by jumping into the MutVar expression.