[Haskell-cafe] MonadFix wiki confusion

[Samuel Rødal]

On Fri, Oct 23, 2015 at 3:14 AM, Albert Y. C. Lai <trebla at vex.net> wrote:
> 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