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

Tyson Whitehead twhitehead at gmail.com
Mon Nov 5 19:00:39 UTC 2018

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
    (length -> x, length -> y) = paritionEithers $ repeat (Left ())

That is, `partitionEithers` is

partitionEithers :: [Either a b] -> ([a],[b])
partitionEithers = foldr go ([],[])
     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 ->
    @ 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

More information about the Haskell-Cafe mailing list