[Haskell-cafe] Re: advantages of using fix to define rcursive functions

[Dan Piponi]

On 7/26/07, Nicolas Frisby <nicolas.frisby at gmail.com> wrote:
> Trying to summarize in one phrase: you can do interesting
> manipulations to functions before applying fix that you cannot do to
> functions after applying fix (conventional functions fall in this
> second category).

Something similar holds for types where we can use something like

data Fix s a = In{out :: s a (Fix s a)}

to construct fixed points of functors, as opposed to functions. Any
recursive type can be expressed using Fix, so the question is, why
would you do it? Well, associated to every recursive type is a
corresponding fold and unfold, of which the familiar foldr and unfoldr
are special cases for the List type. If we define our types using Fix
of some functor, then we can also have fold and unfold built for us
automatically from the functor, alongside the actual type.

There are a number of papers that discuss this, including "The Essence
of the Iterator Pattern" by Jeremy Gibbons and Bruno C. d. S.
Oliveira.
--
Dan