How does the ST monad work?

by

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.

More Related Contents:

  1. What is a monad?
  2. Monads with Join() instead of Bind()
  3. Operating on a return from a Maybe that contains “Just”
  4. A monad is just a monoid in the category of endofunctors, what’s the problem?
  5. Is monad bind (>>=) operator closer to function composition (chaining) or function application?
  6. How to extract value from monadic action
  7. Large-scale design in Haskell? [closed]
  8. What is the purpose of the reader monad?
  9. Is Haskell truly pure (is any language that deals with input and output outside the system)?
  10. Euler 43 – is there a monad to help write this list comprehension?
  11. Haskell: I/O and Returning From a Function
  12. Why does haskell’s bind function take a function from non-monadic to monadic
  13. Expressing do block using only monadic bind syntax
  14. Difference between Monad and Applicative in Haskell
  15. Defining a new monad in haskell raises no instance for Applicative
  16. What is a monad?
  17. Is there a way to place some impure code inside pure functions?
  18. Concrete example showing that monads are not closed under composition (with proof)?
  19. How to use (->) instances of Monad and confusion about (->)
  20. What are free monads?
  21. Why are side-effects modeled as monads in Haskell?
  22. How to interpret bind/>>= of the function instance?
  23. Is there a monad that doesn’t have a corresponding monad transformer (except IO)?
  24. Why should Applicative be a superclass of Monad?
  25. How to enumerate a recursive datatype in Haskell?
  26. How to handle side effect with Applicative?
  27. How to return a pure value from a impure method
  28. In what sense is the IO Monad pure?
  29. How Monads are considered pure?
  30. Is Haskell’s mapM not lazy?

Leave a Comment