The s keeps objects inside the ST monad from leaking to the outside of the ST monad.
-- This is an error... but let's pretend for a moment...
let a = runST $ newSTRef (15 :: Int)
b = runST $ writeSTRef a 20
c = runST $ readSTRef a
in b `seq` c
Okay, this is a type error (which is a good thing! we don't want STRef to leak outside the original computation!). It's a type error because of the extra s. Remember that runST has the signature:
runST :: (forall s . ST s a) -> a
This means that the s on the computation that you're running has to have no constraints on it. So when you try to evaluate a:
a = runST (newSTRef (15 :: Int) :: forall s. ST s (STRef s Int))
The result would have type STRef s Int, which is wrong since the s has "escaped" outside of the forall in runST. Type variables always have to appear on the inside of a forall, and Haskell allows implicit forall quantifiers everywhere. There's simply no rule that allows you to to meaningfully figure out the return type of a.
Another example with forall: To clearly show why you can't allow things to escape a forall, here is a simpler example:
f :: (forall a. [a] -> b) -> Bool -> b
f g flag =
if flag
then g "abcd"
else g [1,2]
> :t f length
f length :: Bool -> Int
> :t f id
-- error --
Of course f id is an error, since it would return either a list of Char or a list of Int depending on whether the boolean is true or false. It's simply wrong, just like the example with ST.
On the other hand, if you didn't have the s type parameter then everything would type check just fine, even though the code is obviously pretty bogus.
How ST actually works: Implementation-wise, the ST monad is actually the same as the IO monad but with a slightly different interface. When you use the ST monad you actually get unsafePerformIO or the equivalent, behind the scenes. The reason you can do this safely is because of the type signature of all ST-related functions, especially the part with the forall.
STmonad as well. Once you understand how rank-2 types can control "who chooses" the type used for a type variable, that should help you understand howSToperations use rank-2 to prevent its computations from being used illicitly. – Luis Casillas Sep 18 '12 at 0:58a :: ST Int Int; a = return 2STis a perfectly ordinary state monad, except it uses an unboxed pair as output of the state functionState# s -> (# State# s, a #)which makes it impractical to deal with. The mystery is entirely inrunSTwhich has a rank 2 type, though ST itself isnt one. – applicative Sep 27 '12 at 2:27