[Haskell-beginners] Cyclic structures

David Tchepak tchepak at gmail.com
Mon Apr 23 08:00:09 CEST 2012

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120423/d22d0495/attachment.htm>

More information about the Beginners mailing list