On Thu, 2005-07-07 at 18:43 +0000, Dinh Tien Tuan Anh wrote:
Hi, Im a newbie to Haskell and the concept of "cyclic strutures" has confused me a lot
I think it can be confusing for most people, so I wouldn't be too concerned. I may not answer your question completely, but I hope to give you an idea of where to start. To understand cyclic structures it is useful to think of "graph reduction", because these graphs allow us to conveniently represent sharing between objects. Cycles are simply "self-sharing".
For example (taken from Richard Bird's book):
ones = 1:ones Its clear that it involves a cyclic structure
Here's a graph representation of that list (needs a fixed width font to view correctly): @<--- / \ | / \_| @ / \ / \ (:) 1 The @ sign represents function application. Note that the top application has a cyclic right argument. A good question is how did this cycle come about? One way of answering this question is to consider how recursion can be implemented in graph reduction. The textbook approach is to say: okay let's introduce a dedicated recursion operator, we'll call it fix (for fixpoint or maybe fixed point). The idea is that all recursive equations in the program can be re-written into non-recursive equations by way of the new fix operator. The intuition is that we want to get rid of the recursive call inside ones. Here's a first step: ones' = \z -> 1 : z I've called it ones' to avoid confusion with the original ones. Now the parameter z takes the place of ones in the right-hand-side. We can try to get back to the original version by applying ones' to itself: ones' ones' Of course this doesn't work because ones is now a function, and the rightmost ones' must also be applied to itself: ones' (ones' ones') Still it doesn't work for the same reason. What we want is a way to apply ones' to itself "forever". That's where fix comes in. It should satisfy this equation: fix f = f (fix f) Thus: fix ones' = ones' (ones' (ones' (ones' ... ) ) ) = 1 : (ones' (ones' (ones' ... ) ) ) = 1 : 1 : (ones' (ones' ...) ) ... So we can tidy things up a bit: ones = fix (\z -> 1 : z) This is the infinite list of ones, but not recursive (though fix is recursive!). So how is fix represented as a graph? Here's one option: fix----> \f | | @ / \ / \ f @ / \ / \ fix f No cycles! Here's another "clever" option: fix---->\f | | @<---- / \ | / \__| f Now a cycle. Note how the cycle captures the notion of a function applied to itself forever. Consider the difference between the two graph implementations of fix in the definition of ones, such that we have: ones---->@ / \ / \ fix \z (looks a bit funny because of the lambda) | | @ / \ / \ @ z / \ / \ (:) 1 Hopefully you can see that the first version of fix will not produce a cycle, but the second one will.
But:
ones = repeat 1 repeat x = x:repeat x
repeat x = xs where xs = x:xs create a cyclic stucture ?
Consider the difference between: repeat = fix (\z x -> x : z x) and: repeat x = fix (\z -> x : z) Draw both graphs that result from using the cyclic version of fix. You should note that only the second graph ends up with a cycle in the tail of the list. I've intentionally skipped over some details, like how to handle where clauses. Grab a textbook to fill in the details. Note that Haskell does not make any requirements as to how recursion should be implemented. Therefore there is no guarantee how much sharing you will get - it depends on the details of the compiler. However, all the popular compilers seem to implement something akin to the cyclic version of fix. Cheers, Bernie.