[Haskell-cafe] Why doesn't this consume all the computer's memory?

[Tyson Whitehead]

I take back my follow up comment.  I still don't understand why there
isn't a buildup of thunks.

I've written an updated/simplified variant and posted it on
r/haskellquestions.  Hopefully someone will enlighten me.

https://www.reddit.com/r/haskellquestions/comments/9v6z49/why_does_this_code_not_eat_all_the_memory_and_die/

Thanks!  -Tyson
On Mon, 5 Nov 2018 at 14:25, Tyson Whitehead <twhitehead at gmail.com> wrote:
>
> I believe I actually figured it out.  There is not buildup because y
> is just forever bound to
>
> y = length . snd $ paritionEithers $ repeat (Left ())
>
> I guess the thing to realize is that this function will traverse the
> list twice.  That is, what I wrote is essentially
>
> x = length . fst $ paritionEithers $ repeat (Left ())
> y = length . snd $ paritionEithers $ repeat (Left ())
>
> where both x and y independently traverse the entire list repeating
> any work that needs to be done to generate the elements.
>
> Thanks!  -Tyson
> On Mon, 5 Nov 2018 at 14:00, Tyson Whitehead <twhitehead at gmail.com> wrote:
> >
> > I would expect the following to consume all the computer's memory and
> > die due to a buildup of lazy pattern matches for the `y` value.
> >
> > ```
> > import Data.Either
> >
> > main = print x >> print y
> >   where
> >     (length -> x, length -> y) = paritionEithers $ repeat (Left ())
> > ```
> >
> > That is, `partitionEithers` is
> >
> > ```
> > partitionEithers :: [Either a b] -> ([a],[b])
> > partitionEithers = foldr go ([],[])
> >    where
> >      go (Left  x) ~(xs,ys) = (x:xs,ys)
> >      go (Right y) ~(xs,ys) = (xs,y:ys)
> > ```
> >
> > and, in the -ddump-simpl we see the `go Left` branch returns a thunk
> > on both the right and left sides that hold onto the evaluation of
> > (x:xs,ys) as we would expect
> >
> > ```
> > Left x_aqy ->
> >   (GHC.Types.:
> >     @ a_a1q8 x_aqy
> >   (case ds1_d1rO of { (xs_aqz, ys_aqA) -> xs_aqz }),
> >    case ds1_d1rO of { (xs_aqz, ys_aqA) -> ys_aqA });
> > ```
> >
> > Our code keeps generating more and more of these thunks as the
> > left-hand side chases down the infinite list of `Left ()` values, and
> > the machine cannot let go of them because, as far as it knows, we are
> > going to reach the end sometime and then need the right-hand side.
> >
> > Thus I expect it would consume all the memory and crash.  But it
> > doesn't.  It just sits there forever consuming 100% CPU at a constant
> > memory limit.  This means my mental model is defective and I'm unable
> > to properly reason about the space usage of my programs.
> >
> > Could someone please enlighten me as to were I'm missing?  Is there
> > some sort of optimization going on here?  When can it be depend on?
> >
> > Thanks very much!  -Tyson
> >
> > I would expect