On Fri, Oct 23, 2015 at 3:14 AM, Albert Y. C. Lai
This shows a wrong concept.
When you write this kind of code:
return (x+y, a+b)
the tuple is not constructed lazily. The tuple is constructed here and now.
To be sure, the sub-value x+y is constructed lazily, but then you would say "x+y is constructed lazily", not "the tuple is constructed lazily". Similarly for a+b. And to say both at once, you would say "the tuple content is constructed lazily", not "the tuple is constructed lazily".
The tuple itself --- a machine word standing for the data constructor (,), followed by a pointer to the thunk for x+y, followed by a pointer to the thunk for a+b --- is constructed here and now.
I see now that calling the tuple "lazily constructed" is incorrect. I assume it would be better to call it a lazy pair? In contrast to this implementation of "strict pairs": https://hackage.haskell.org/package/strict-0.3.2/docs/Data-Strict-Tuple.html
Furthermore, if the code goes like this:
return (B n x y, a+b)
then not only the tuple, but also the B n x y ("the tree value"), are constructed here and now.
Are you sure about that? By exchanging return $ (B s l' r', i + sl + sr) with let tree = B s l' r' return $ tree `seq` (tree, i + sl + sr) and having the tree data structure be strict as you suggested in the article: data BTree = Z | B !Int !BTree !BTree deriving Show I experience the hang. Maybe I'm just confused about the use of the word "constructed".
Again, to be sure, this code is lazy on n, on x, and on y. But the tree value --- a machine word standing for the data constructor B, followed by a pointer to n, followed by a pointer to x, followed by a pointer to y --- is constructed here and now.
* * *
Guess what, neither can you fall back to "the content of the tuple, and/or the content of the tree value, is constructed lazily". Because it is readily refuted by an experiment.
And it should be natural to think up this experiment because every time you conjecture "this works because the code is lazy on xxx" the first instinct should be "so let me run an experiment in which I force evaluatation of xxx ASAP to test the conjecture".
Yep, I also ran some experiments, which is how I found that forcing evaluation of the strict tree caused the overall evaluation to hang.
So here it goes:
{-# LANGUAGE RecursiveDo #-}
import Control.Exception (evaluate)
data BTree = Z | B Int BTree BTree deriving Show
repsum t = do rec (u,s) <- rep_x_sum t s putStrLn "" return u
rep_x_sum Z _ = return (Z, 0) rep_x_sum (B i l r) s = do putStr "(" (l',sl) <- rep_x_sum l s putStr (show i) (r',sr) <- rep_x_sum r s putStr ")" evaluate l' evaluate r' tree <- evaluate (B s l' r') sum <- evaluate (i + sl + sr) tuple <- evaluate (tree, sum) return tuple
main = repsum (B 4 (B 3 Z Z) (B 5 Z (B 1 Z Z))) >>= print
This experiment hastens evaluation of the tuple content and most of the tree content; for good measure, evaluate the tuple and the tree, too, whether it is redundant or not.
Run this experiment. See it doesn't hang. Use this observation to refute many, many hypotheses.
The only content left unevaluated is s. Laziness in s is the only laziness needed. But then I already wrote that in the article, didn't I?
"The laziness needed is just in the rep_x_sum algorithm: it does not evaluate s."
But in your new example the tree data structure is no longer strict. I agree that the only laziness that's needed is to not evaluate s, and making the tree strict in the original code doesn't cause that as the tuple is still lazy. I just thought the article could be a bit more explicit about that to avoid confusion. -- Samuel