[Haskell-cafe] Confused about Cyclic struture

[Bernard Pope]

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.