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

[Tyson Whitehead]

Sorry for all the noise.  I believe I finally tracked down the eat all
the memory/don't eat all the memory trigger.  It is the view pattern.

When I calculate the length in a view pattern, memory stays constant,
when I calculate it outside, it explodes.

I'll have to examine the simpl dump some more to see if I can figure
out the difference between these two.  Sorry for the noise on the
list.

Cheers!  -Tyson
On Wed, 7 Nov 2018 at 23:42, Tyson Whitehead <twhitehead at gmail.com> wrote:
>
> 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