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.

Peripheral

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. – Brokerage

Yes, that was the solution that I found. @luqui has also been commenting on this on [#24068899 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. – Peripheral

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. – Brokerage

Answer 1

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.

Arlyn

Thank you for taking the time, it checks out. From the previous discussions it seems like Data.STRef is stricter for a reason. – Peripheral

I would even risk saying that is is impossible for it to be fully lazy in general, because unlike the plain old State monad for which allocation is performed by runState, and therefore everything before a State.put can be ignored, it needs to dynamically allocate new space for each newSTRef. There is a possible optimization that comes to mind, however: for STRefs over different types, the newSTRef, readSTRef, writeSTRef operations could be lazily interleaved. – Peripheral

@hpacheco: Concerning State: It doesn't get ignored per se, but instead uses an irrefutable pattern which makes it just lazy enough so that we can have that effect. An operation on STRef on the other hand changes the state, either the RealWorld, or the thread of execution s. That's deeply implemented in read|new|write|modifyMutVar. A real lazy STRef would need to collect actions and then collaps them after the total actions have been parsed. Whether this is possible without unsafeInterleaveST, I don't know. I'm still pretty new to Haskell :). – Arlyn