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

[Tyson Whitehead]

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