On Mon, Apr 23, 2012 at 8:00 AM, David Tchepak
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ï