Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Lazy state + IO not lazy? (Jan Snajder)
2. Re: Lazy state + IO not lazy? (Kim-Ee Yeoh)
----------------------------------------------------------------------
Message: 1
Date: Mon, 03 Nov 2014 18:45:17 +0100
From: Jan Snajder <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Lazy state + IO not lazy?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8; format=flowed
Dear all,
On 10/27/14, Kim-Ee Yeoh <[email protected]> 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
------------------------------
Message: 2
Date: Tue, 4 Nov 2014 16:27:27 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Lazy state + IO not lazy?
Message-ID:
<CAPY+ZdQY4JcF0AvguzO2yRXaMr+Xb6Go=M4ppSiQ2akGR=g...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Hey Jan,
Your answers are fine. You're reasoning at a high-level which is okay,
and if you want to get into the details, you'll have to inline the
StateT abstraction and reason directly with the low-level code.
> 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
Both expressions are identical save for one letter.
But what's hidden is a third:
head `fmap` mapM return (1:undefined) :: IO Int
The gotcha is that expr no. 2, by virtue of operating in StateT over
IO, must match the behavior of no. 3, because the monadic space
contains all of IO.
Put another way, no. 1 and 2 are so similar syntactically, you'd think
their values must match. But no, the monadic semantics of s -> IO (a,
s) are such that it's no. 3 that no. 2 must match with.
> From this I conclude that the second monad is strict, whereas the first
> is not. Is that correct?
So we've seen that Lazy.StateT is strict /in the effects/. Which
prompts the question, well, how is it lazier than Strict.StateT then,
for which this five-year-old posting helps answer:
http://marc.info/?l=haskell-cafe&m=123618429420650
> Assuming that is correct, does this mean that
> every monad stacked on top of an IO monad becomes strict??
In the sense of strict in the effects, I believe so but I haven't
checked all cases.
> Here's another example that illustrates this point:
> http://pastebin.com/0fAFmufA
>
> Why is (4) not computed in constant space, whereas (3) is?
For the same reason that the traversable functions sequence and mapM
diverge on infinite lists when working in IO.
Unless you take the lazy I/O way out.
> 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?
An IO mapM on an infinite list results in an /infinitely IO-effectful/
monadic value.
Which is why mapM return diverges, even when each of those infinity of
effects is null. Like why sum [0,0..] doesn't terminate either. Watch
what happens when you replace "mapM return" by the moral equivalent of
"return".
The triple combo of traversable + IO + infinite list is bound to fail.
Without recourse to lazy I/O, that is.
-- Kim-Ee
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 77, Issue 1
****************************************
