Why is there a space leak here?

[Claus Reinke]

> Alastair David Reid wrote:
> > Executive summary: David's program has an incredibly subtle space leak
> > in it (or I'm being incredibly dumb).  I encourage the honchos (and
> > would be honchos) to have a look.  Users of other compilers might give
> > it a shot too.

I think there have been several good explanations already, or
is there anything wrong with them?

As Olaf pointed out, one might use GHood for the job:
http://www.cs.ukc.ac.uk/people/staff/cr3/toolbox/haskell/GHood/

An example on how to add observations in this case, and 
how to interpret the results might be helpful to those who 
haven't used GHood.

1. Code:

import Observe

foo1 m
   = take m (observe "v-out" v)
     where
       v = 1 : concat (map triple (observe "v-in" v))
       triple x = [x,x,x]

main = printO $ (foo1 100::[Int])

2. Interpretation:

Using Hugs to generate the observations, you should see the two
views of v evolving just as other mails in this thread have explained,
i.e., "v-out" grows at three times the rate of "v-in". Remembering
that these are two views of the same structure, the problem is that
generating "v-out" depends on "v-in", which is "v-out";-) which means 
that the program execution should hold on to whatever "v-out" 
delivers until observers of "v-in" are through with it. In simpler words: 
 
    "v-out to v-in: you ain't seen nothing yet!".

3. Variation:

Wojciech suggested that nhc's behaviour seems to differ slightly,
which prompted me to try whether this would be visible in GHood.

For explanation: Hood is portable, in that it works with most Haskell 
implementations (special version make use of more features, when 
available, and cater for renamed IOExtras..), but as it instruments 
those Haskell implementations to do its work, its observations can 
actually depend on what the implementation does.

As GHood shows you observations in more detail, you'll see even
more differences (such as: evaluation order of additions in nhc98
seems to depend on the type;-).
 
Trying the code above with nhc98-1.02 and the matching variant
of Observe.lhs, you'll see something odd: instead of two views of
v evolving in parallel, further copies of the "v-in"-view are created.
So, every three elements in "v-out", we need another element of
"v-in"(1), every three elements in "v-in"(1), we seem to need another
element of "v-in"(2), etc. 

Perhaps Malcolm can explain what nhc98 does with this example?

Oh, and for all the honchos Alastairs referred to: I seem to 
remember that the work on preserving cycles with lazy memo
functions also had some comments about avoiding unnecessary
growth of cyclic structures. Can anyone figure out how to apply
that to this example (or tell me that it is impossible)?

Hth,
Claus

PS: Getting new email in before sending this off, I see that
      some explainers now refer to themselves as foolish, but
      I'll send this off anyway, at the risk of adding myself to
      that foolish Haskell programmers club:-)