[Haskell-beginners] Lazy state + IO not lazy?

[Jan Snajder]

Dear all,

On 10/27/14, Kim-Ee Yeoh <ky3 at atamo.com> wrote:

Kim-Ee, many thanks for your reply and sorry for my delayed reaction.

> Consider
>
>    let u = return () :: IO () in
>    expr >> u
>
> where expr ranges over (return undefined), (undefined), and (error "urk").

Ok, so this is what we get:

(1)
return undefined >> return () :: IO ()
==> evaluates to 'IO ()'

(2)
 > undefined >> return ()
*** Exception: Prelude.undefined

(3)
 > error "urk" >> return ()
*** Exception: ur

 > Are their executions surprising?

In my understanding, in a strict state monad, the '>>' operator will 
evaluate the (value,state) pair of the left expression up to the (,) 
constructor. Assuming this is correct, in (1) 'return undefined' gives a 
'(undefined,state)', which is not evaluated further, hence the 
computation continues. In (2), there is no 'return' to create a 
(value,state) pair, so when '>>' tries to evaluate the left expression, 
it evaluates directly to undefined. The same holds for error, which (I 
guess) stops the execution immediately upon being evaluated.

Is my reasoning correct?

> Compare to
>
>    let u = return () :: State Int () in
>    evalState (expr >> u) 0
>
> for both strict and lazy state.

Ok, here we go:

 > Strict.evalState (return undefined >> return () :: Strict.State Int ()) 0
()

 > Strict.evalState (undefined >> return () :: Strict.State Int ()) 0
*** Exception: Prelude.undefined

 > Strict.evalState (error "urk" >> return () :: Strict.State Int ()) 0
*** Exception: urk

 > Lazy.evalState (return undefined >> return () :: Lazy.State Int ()) 0
()
 > Lazy.evalState (undefined >> return () :: Lazy.State Int ()) 0
()
 > Lazy.evalState (error "urk" >> return () :: Lazy.State Int ()) 0
()

So, strict-state monad matches the behavior of 'IO', which is what I 
expected because I know 'IO' is a strict-state monad.

Furthermore, lazy-state monad never inspects the left argument of '>>', 
so all three cases compute.

 > IO above matches one of them. Suppose
> IO's behavior matches the other, what happens?

I guess the IO monad would behave in an undesirable way because we would 
not be able to raise an exception nor catch undefined computations. Is 
that what you meant?

> Now with the definition of mapM in mind, consider the difference
> between your original:
>
>    Lazy.evalStateT (head `fmap` mapM return (1:undefined)) 0
>
> and
>
>    Lazy.evalStateT (head `fmap` mapM return [1,undefined]) 0
>
> Did you mean the latter?

No, that's not what I meant. But I assume that in the latter case we 
won't get a bottom because we don't evaluate beyond the spine of the list:

 > Lazy.evalState (head `fmap` mapM return [1,undefined]) 0
1
 > Lazy.evalStateT (head `fmap` mapM return [1,undefined]) 0
1

Is my interpretation correct?

But what confuses me why we get different behavior here:

 >  Lazy.evalState (head `fmap` mapM return (1:undefined)) 0
1
 >  Lazy.evalStateT (head `fmap` mapM return (1:undefined)) 0
*** Exception: Prelude.undefined

 From this I conclude that the second monad is strict, whereas the first 
is not. Is that correct? Assuming that is correct, does this mean that 
every monad stacked on top of an IO monad becomes strict??

Here's another example that illustrates this point:
http://pastebin.com/0fAFmufA

Why is (4) not computed in constant space, whereas (3) is?

Finally, what ultimately bothers me is the following:
is it true that if my state monad is built on top of an IO monad I 
cannot lazily consume a result of a mapM computation?

(Here I am assuming, perhaps wrongly, that if '>>=' is non-strict in its 
left argument, then 'sequence' is tail recursive modulo cons. But I'm 
actually not convinced why this should be the case.)

Many thanks for any input!

Cheers,
Jan