Why is there a space leak here?

[kahl@heraklit.informatik.unibw-muenchen.de]

David Bakin <davidbak@cablespeed.com> writes:

 > Which of the various tools built-in or added to Hugs, GHC, NHC, etc. would
 > help me visualize what's actually going on here?  I think Hood would (using
 > a newer Hugs, of course, I'm going to try it).  What else?

I just used my old ghc-4.06 add-in ``middle-end'' ``MHA'' to generate
a HOPS module from David's message (slightly massaged, appended below),
and then used HOPS to generate two animations:

http://ist.unibw-muenchen.de/kahl/MHA/Bakin_foo1_20.ps.gz
http://ist.unibw-muenchen.de/kahl/MHA/Bakin_foo2_20.ps.gz

Hold down the space key in ghostview to get the animation effect!

The left ``fan'', present in both examples, is the result list,
and only takes up space in reality as long as it is used.
The right ``fan'', visible only in foo1, contains the cycle
of the definition of v, and represents the space leak.
The take copies cons node away from the cycle.

The HOPS input was generated automatically by an unreleased
GHC ``middle end'' that is still stuck at ghc-4.06.

The homepage of my term graph programming system HOPS is:

http://ist.unibw-muenchen.de/kahl/HOPS/


Wolfram




> module Bakin where

-- This has a space leak, e.g., when reducing (length (foo1 1000000))

> foo1 :: Int -> [Int]
> foo1 m
>   = take m v
>     where
>       v = 1 : flatten (map triple v)
>       triple x = [x,x,x]

-- This has no space leak, e.g., when reducing (length (foo2 1000000))

> foo2 :: Int -> [Int]
> foo2 m
>   = take m v
>     where
>       v = 1 : flatten (map single v)
>       single x = [x]

-- flatten a list-of-lists

> flatten :: [[a]] -> [a]
> flatten []             = []
> flatten ([]:xxs)       = flatten xxs
> flatten ((x':xs'):xxs) = x' : flatten' xs' xxs
> flatten' [] xxs        = flatten xxs
> flatten' (x':xs') xxs  = x': flatten' xs' xxs