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

[Tom Ellis]

It can't be as simple as you make out.  The semantics of ViewPatterns cannot
be such that

   (length -> x, length -> y) = partitionEithers $ repeat (Left ())

means 

   x = length . fst $ partitionEithers $ repeat (Left ())
   y = length . snd $ partitionEithers $ repeat (Left ())

It must surely mean

   (px, py) = partitionEithers $ repeat (Left ())
   x = length px
   y = length py
  
With that interpretation my by-hand evaluations show a space leak, see
below.  The only way I can reconcile this with the observed behaviour is
that GHC's garbage collector can "see through" simple case statements.  I
vaguely remember reading something like this.

Can any GHC developer confirm?

Tom




main = print x >> print y
  where
    (length -> x, length -> y) = partitionEithers $ repeat (Left ())

main = 
    case (partitionEithers (repeat (Left ()))) of (px, py) ->
        let x = length px
            y = length py
        in print x >> print y

(let z = ([], []))

main = 
    case (foldr go z (repeat (Left ()))) of (px, py) ->
        ...

main = 
    case (foldr go z (Left () : repeat (Left ()))) of (px, py) ->
        ...

main = 
    case (go (Left ()) (foldr go z (repeat (Left ()))) of (px, py) ->
        ...

main = 
    case (let t = foldr go z (repeat (Left ()))
          in (fst t, snd t)) of (px, py) ->
        ...

t = foldr go z (repeat (Left ()))
main = 
    case (fst t, snd t) of (px, py) ->
        ...

t = foldr go z (repeat (Left ()))
main = 
    case (fst t, snd t) of (px, py) ->
        ...

t = foldr go z (repeat (Left ()))
main = let x = length (fst t)
           y = length (snd t)
       in print x >> print y
       
t = foldr go z (repeat (Left ()))
main = let x = length (fst t)
           y = length (snd t)
       in print x >> print y

(omitting a few steps ...)

t = go (Left ()) z (foldr go z (repeat (Left ())))
main = let x = length (fst t)
           y = length (snd t)
       in print x >> print y

t = let t2 = foldr go z (repeat (Left ()))
    in (fst t2, snd t2)
...

t = (fst t2, snd t2)
t2 = foldr go z (repeat (Left ()))
...

t = (fst t2, snd t2)
t2 = (fst t3, snd t3)
t3 = foldr go z (repeat (Left ()))
...

t = (fst t3, snd t2)
t2 = (fst t3, snd t3)
t3 = foldr go z (repeat (Left ()))
...


On Mon, Nov 05, 2018 at 02:25:50PM -0500, Tyson Whitehead 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?