[Haskell-cafe] WriterT [w] IO is not lazy in reading [w]

[Ryan Ingram]

2008/12/31 Paolino <paolo.veronelli at gmail.com>:
> I must ask why runWriterT k :: State s (a,[Int]) is working.
> Looks like I could runIO the same way I evalState there.
> In that case I wouldn't wait for the State s action to finish.
>
> Thanks

Assuming you have Control.Monad.State.Lazy (which I think is the
default), here is the difference:

(>>=) for State:

ma >>= f = State $ \s0 ->
    let (a, s1) = runState ma s0
    in runState (f a) s1

The "let" is a lazy pattern match; in particular, consider this code:

    runState (do
        put 0
        put 1) 2

-> desugar
    runState (put 0 >> put 1) 2

The rest is lazy evaluation in action!
-> apply >>
    runState (put 0 >>= \_ -> put 1) 2

-> apply >>=
    runState (State $ \s0 ->
        let (a, s1) = runState (put 0) s0
        in runState (put 1) s1
    ) 2

-> apply runState
    (\s0 ->
        let (a,s1) = runState (put 0) s0
        in runState (put 1) s1
   ) 2

-> beta reduce
    let s0 = 2 in
    let (a,s1) = runState (put 0) s0
    in runState (put 1) s1

-> apply put
    let s0 = 2 in
    let (a,s1) = runState (put 0) s0
    in runState (State $ \_ -> ((), 1)) s1

-> apply runState
    let s0 = 2 in
    let (a,s1) = runState (put 0) s0
    in (\_ -> ((), 1)) s1

-> beta reduce
    let s0 = 2 in
    let (a,s1) = runState (put 0) s0
    in ((), 1)

-> garbage collect
    ((), 1)

Note that at no point were s0, a, or s1 evaluated; so there was no
need to evaluate the state at all!  Furthermore, even if you replace
(put 0) with a computation that loops and looks at the state at each
point, the result is immediately a pair, so future computation can
continue.  Now lets contrast with IO:

(>>=) for IO (taking out the "unboxed pairs" stuff which muddles the issue)

ma >>= f = IO $ \s0 ->
    case (unIO ma s0) of
        (a, s1) -> unIO (f a) s1

(Note that this is the basically the same as Control.Monad.State.Strict)

Consider

main = do
    putStrLn "hello"
    putStrLn "world"

We'll use this definition of putStrLn for simplicity's sake:

> -- primitive, unsafe, side-effecting function.
> putStrLn# :: String -> ()
>
> putStrLn :: String -> IO ()
> putStrLn s = IO $ \w -> seq (putStrLn# s) ((), w)

So putStrLn is an IO action which takes a "world" (a dummy value that
doesn't really exist) as input, and before it gives any output, forces
the evaluation of a side-effecting primitive function via seq.  It
then returns a pair containing the result (), and the original "world"
argument as the state.

Desugar:
    main = (putStrLn "hello" >> putStrLn "world")

Send to the runtime:
    unIO (putStrLn "hello" >> putStrLn "world") world#

Now lets evaluate it.

-> Apply >>
    unIO (putStrLn "hello" >>= \_ -> putStrLn "world") world#

-> Apply >>=
    unIO (IO $ \w0 -> case unIO (putStrLn "hello") w0 of
        (a, w1) -> unIO ((\_ -> putStrLn "world") a) w1

-> Apply unIO and beta-reduce
    case unIO (putStrLn "hello") world# of
        (a, w1) -> unIO ((\_ -> putStrLn "world") a) w1

Note that the evaluation order is different here; since we have a case
statement, we must force the evaluation of the first putStrLn to make
sure it evaluates to a pair!

-> Apply putStrLn
    case unIO (IO $ \w -> seq (putStrLn# "hello") ((), w)) world# of
        (a, w1) -> unIO ((\_ -> putStrLn "world") a) w1

-> apply unIO & beta-reduce
    case seq (putStrLn# "hello") ((), world#) of
        (a, w1) -> unIO ((\_ -> putStrLn "world") a) w1

-> seq evaluates putStrLn#, side effect happens here!
    case ((), world#) of
        (a, w1) -> unIO ((\_ -> putStrLn "world") a) w1

-> pattern match in case succeeds now
    let a = ()
        w1 = world#
    in unIO ((\_ -> putStrLn "world") a) w1

-> beta reduce & garbage collect
    unIO (putStrLn "world") world#

-> apply putStrLn
    unIO (IO $ \w -> seq (putStrLn# "world") ((), w)) world#

-> apply unIO & beta reduce
    seq (putStrLn# "world") ((), world#)

-> seq evaluates putStrLn#, side effect happens here!
    ((), world#)

Now,  you are probably wondering for the reason behind the use of
"case" vs. "let".  It's pretty simple; lets evaluate that last code
using the lazy method like State.  Everything is the same up to "apply
>>=", so start there:

    unIO (putStrLn "hello" >>= \_ -> putStrLn "world") world#

-> Apply >>=
    unIO (IO $ \w0 ->
        let (a, w1) = unIO (putStrLn "hello") w0
        in unIO (putStrLn "world") w1
    ) world#

-> apply unIO and beta-reduce
    let (a, w1) = unIO (putStrLn "hello") world#
    in unIO (putStrLn "world") w1

-> apply putStrLn (the second one!)
    let (a, w1) = unIO (putStrLn "hello") world#
    in unIO (IO $ \w -> seq (putStrLn# "world") ((), w)) w1

-> apply unIO and beta-reduce
    let (a, w1) = unIO (putStrLn "hello") world#
    in seq (putStrLn# "world" w1) ((), w1)

Now we call putStrLn# which causes a side effect.  It ignores the
"world" argument and just returns it unchanged, of course.  We could
also add extra machinery to the compiler to force it to treat the
"world" argument as strictly, but you can see that using "lazy" really
changes the order of evaluation, which ends up making the code much
harder to optimize.

-> seq evaluates putStrLn# (printing "world", oops!)
    let (a,w1) = unIO (putStrLn "hello" world#)
    in ((), w1)

We need w1 here, so we have to force evaluation of the pair to extract it.

-> apply putStrLn
    let (a,w1) = unIO (IO $ \w -> seq (putStrLn# "hello") ((), w)) world#
    in ((), w1)

-> apply unIO & beta-reduce
    let (a,w1) = seq (putStrLn# "hello") ((), world#)
    in ((), w1)

-> seq evaluates putStrLn#, printing "hello"
    let (a,w1) = ((), world#)
    in ((), w1)

-> garbage-collect
    ((), world#)

I've omitted some of the details, and this isn't exactly how it works.
 In particular, I believe GHC's primitive operations take the World#
argument directly, so you can argue that this behavior wouldn't happen
as long as that argument was considered "strict".  But the "lazy"
behavior makes the order of evaluation much harder to predict, which I
think is considered to be bad for IO, which lives on the "imperative"
side of the imperative/functional divide.  In particular,
unsafeInterleaveIO (and its friend getContents) would be even more
difficult to use correctly if IO used a "lazy state" monad.

It might be possible to build a "lazy-ify" monad transformer which
would make this work.  In particular, I think Oleg's LogicT
transformer[1] does something of the sort, only applying side effects
where they are required in order to get "the next result" in a
nondeterministic computation.

  -- ryan

[1] http://okmij.org/ftp/Computation/monads.html#LogicT