Haskell: How lazy is the lazy `Control.Monad.ST.Lazy` monad?

Question

I have been experimenting with the strict and lazy ST monads, and I do not understand clearly the degree of laziness of each. For example, using the lazy Control.Monad.State.Lazy monad we can write:

main = print $ (flip evalState) "a" $ do
    forever $ put "b"
    put "c"
    get

This works fine and outputs "c". Dually, the same code for the strict Control.Monad.State.Strict variant will run put "b" forever, and hang.

Intuitively, I would expect the same duality to hold for the ST monads. That is, given the code:

main = print $ S.runST $ do
        r <- newSTRef "a"
        forever $ writeSTRef r "b"
        writeSTRef r "c"
        readSTRef r

Control.Monad.ST.Lazy should output "c", while Control.Monad.ST.Strict should hang. However, they both loop indefinitely. I believe that there is a valid reason for this, like: reading backwards, the reference r is not yet allocated at the time that the last writeSTRef is called. But it somehow feels like we could do better.

You could use Control.Monad.Lazy.Unsafe.unsafeInterleaveST $ forever $ writeSTRef r "b" to get the laziness you're looking for. Without knowing more about your problem though, I can't say if doing so is actually safe. — John L
Yes, that was the solution that I found. @luqui has also been commenting on this on [stackoverflow.com/questions/24068399/… thread). forever was kind of an exaggeration, because it seems like you at least need to trace the history of modifications backwards (not evaluating the ones over the same reference I hope) to the point of creation. — hpacheco
Oh I should point out that unsafeInterleaveST means to defer evaluation of its argument until the result value is needed. Which means if you ignore the result of unsafeInterleaveST (as in my comment), you may as well just delete that line. unsafeInterleave* functions are really meant for creating codata such as lists. — John L

Zeta Zeta · Accepted Answer · 2014-06-06T15:50:01

How lazy is the lazy Control.Monad.ST.Lazy monad?

Surprisingly, it is perfectly lazy. But Data.STRef.Lazy isn't.

`ST.Lazy` is lazy

Lets focus on another example for a second:

import qualified Control.Monad.ST as S
import qualified Control.Monad.ST.Lazy as L

squared :: Monad m => m [Integer]
squared = mapM (return . (^2)) [1..]

ok, oops :: [Integer]
ok   = L.runST squared
oops = S.runST squared

Even though ok and oops should do the same, we can get only the elements of ok. If we would try to use head oops, we would fail. However, concerning ok, we can take arbitrarily many elements.

Or, to compare them to the non-monadic squared list, they behave like:

ok, oops :: [Integer]
ok'   = map (^2) [1..]
oops' = let x = map (^2) [1..] in force x -- Control.DeepSeq.force

That's because the strict version evaluates all state operations, even though they're not required for our result. On the other hand, the lazy version delays the operations:

This module presents an identical interface to Control.Monad.ST, except that the monad delays evaluation of state operations until a value depending on them is required.

What about `readSTRef`?

Now lets focus again on your example. Note that we can get an infinite loop with even simpler code:

main = print $ L.runST $ do
    forever $ return ()
    r <- newSTRef "a"
    readSTRef r

If we add an additional return at the end …

main = print $ L.runST $ do
    forever $ return ()
    r <- newSTRef "a"
    readSTRef r
    return "a"

… everything is fine. So apparently there's something strict in newSTRef or readSTRef. Lets have a look at their implementation:

import qualified Data.STRef as ST

newSTRef        = strictToLazyST . ST.newSTRef
readSTRef       = strictToLazyST . ST.readSTRef
writeSTRef  r a = strictToLazyST (ST.writeSTRef r a)

And there's the culprit. Data.STRef.Lazy is actually implemented via Data.STRef, which is meant for Control.Monad.ST.Strict. strictToLazyST only hides this detail:

strictToLazyST :: ST.ST s a -> ST s a
strictToLazyST m = ST $ \s ->
Convert a strict ST computation into a lazy one. The strict state thread passed to strictToLazyST is not performed until the result of the lazy state thread it returns is demanded.

Now lets put things together:

in main, we want to print the value given by the lazy ST computation
the lazy ST computation's value is given by a lazy readSTRef
the lazy readSTRef is actually implemented as a lazy wrapper around the strict readSTRef
the strict readSTRef evaluates the state as if it was a strict one
the strict evaluation of forever $ return () bites us

So the current ST.Lazy is lazy enough. It's the Data.STRef.Lazy that's too strict. As long as Data.STRef.Lazy is based on strictToLazyST, this behavior will endure.

Haskell: How lazy is the lazy `Control.Monad.ST.Lazy` monad?

1 Answers

ST.Lazy is lazy

What about readSTRef?

`ST.Lazy` is lazy

What about `readSTRef`?