[Haskell-beginners] Cyclic structures

[Chaddaï Fouché]

On Mon, Apr 23, 2012 at 8:00 AM, David Tchepak <tchepak at gmail.com> wrote:
>
>   ones = forever 1
>   forever x = x : forever x

So forever 1 is a list whose first element is 1 and the tail is
forever 1, which itself is a list whose head is 1 and the tail is
forever 1...

> The book then has a re-written version of `forever` that looks like this:
>
>   forever x = zs
>     where zs = x : zs
>

So explicitly, forever 1 is a list called zs whose head is 1 and whose
tail is zs itself.

While both code describe the same list, in the second case the sharing
between the list itself and its head is made explicit ("zs = x : zs"
is recursive data) while in the first, you have a recursive function
where the sharing is not explicit : the default with a recursive
function is to evaluate it and recursively evaluate the calls to
itself in the body of the function, there's no reason to think the
result of the recursive call is the same as the main call... Here of
course this is the case, but to automatically recover the sharing is
only an optimisation in certain cases, in some others it is in fact a
catastrophe :

> stuff n = (sum [1..n], length [1..n])

Here the naive version will work in constant memory while the version
where the sharing was recovered ( let xs = [1..n] in (sum xs, length
xs) ) will take O(n) memory...

In other words, GHC is very cautious about recovering sharing, so if
you want it you better be explicit about it by giving yourself a name
to the shared part like in the second version of forever.

-- 
Jedaï