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

Nicolas Frisby nicolas.frisby at gmail.com
Thu Jul 26 17:00:57 EDT 2007


Another advantage here - an analog I'm always eager to point out - is
that just as we can augment functions if they haven't yet been fixed,
we can augment functors. One can extend datatypes and functions (a la
open functions) or generically generate constructs such as (co-)free
(co-)monads in this way.

On 7/26/07, Dan Piponi <dpiponi at gmail.com> wrote:
> 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>


More information about the Haskell-Cafe mailing list