I'm currently reading the first edition of "Introduction to Functional Programming" by Richard Bird and Philip Wadler. Section 7.6 is on cyclic structures, and has the following example: ones = forever 1 forever x = x : forever x Which, after 5 evaluations, produces a graph like: 1 : 1 : 1 : 1 : 1 : forever 1 The book then has a re-written version of `forever` that looks like this: forever x = zs where zs = x : zs Which instead produces a cyclic structure: * 1 : ^-----| So it takes up a fixed amount of space, despite being an infinite list. I was hoping someone could explain the difference between the first and second `forever`s for me. Does the second version become a cyclic graph because the `zs` intermediate expression has no additional arguments so doesn't need to be reduced further? Or do both end up being optimised the same by GHC? (my newbie attempts to profile show the second takes up a bit less space, but I'm not sure if I'm measuring it right). Appreciate any help. Regards, David
Hi, I do not have the answer to your question, but you might be interested in the video about streams by Graham Hutton: http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Graham-Hutton-How-To-B... Adrien On Mon, 23 Apr 2012 16:00:09 +1000, David Tchepak wrote:
Im currently reading the first edition of "Introduction to Functional Programming" by Richard Bird and Philip Wadler. Section 7.6 is on cyclic structures, and has the following example:
ones = forever 1 forever x = x : forever x
Which, after 5 evaluations, produces a graph like:
1 : 1 : 1 : 1 : 1 : forever 1
The book then has a re-written version of `forever` that looks like this:
forever x = zs where zs = x : zs
Which instead produces a cyclic structure:
* 1 : ^-----|
So it takes up a fixed amount of space, despite being an infinite list.
I was hoping someone could explain the difference between the first and second `forever`s for me. Does the second version become a cyclic graph because the `zs` intermediate expression has no additional arguments so doesnt need to be reduced further? Or do both end up being optimised the same by GHC? (my newbie attempts to profile show the second takes up a bit less space, but Im not sure if Im measuring it right).
Appreciate any help. Regards, David
-- Adrien Haxaire www.adrienhaxaire.org | @adrienhaxaire
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ï
participants (3)
-
Adrien Haxaire -
Chaddaï Fouché -
David Tchepak