Why is there a space leak here?

Tom Moertel tom-list-haskell@moertel.com
Tue, 05 Jun 2001 17:17:41 -0400

"Wojciech Moczydlowski, Jr" wrote:
> How come then that the very program compiled under nhc98 evaluates without
> any problem, with memory usage below 1M during its execution?

My claim was that v (as defined) grew faster than it could be consumed,
not that (length (foo1 n)) couldn't be evaluated in constant space.

Even so, your results suggest that nhc98 is doing something
interesting.  Does the memory usage remain constant even if you take 10
or 100 times the number of elements?  If so, perhaps nhc98 is smart
enough to know that

    length (take n x) = n

for all infinite lists x.  It might apply those smarts to optimize out
the expansion of v in foo1 when foo1's result is used as the argument of
length.  Out of curiosity, what happens if you consume those elements
with foldl' (+) 0 rather than length?  

Alternatively, if nhc98 were smart enough to prove that

    foo1 n = replicate n 1

it could do away with v altogether, which would also explain the
interesting behavior.  And if nhc does *that*, my hat's off to the nhc98

Or, if your constants are hard-coded, perhaps nhc98 is evaluating the
(length foo1 1000000) expression at compile time.  What happens to
memory consumption if foo1's argument is supplied at run time?

Or maybe I'm mistaken about v.  Wouldn't be the first time I've done
something boneheaded.  ;-)

In any case, I am curious about what nhc98 is doing internally.  Any