voigt:

Donald Bruce Stewart wrote:

...

harald.rotter:

...

Hi,

I read about the usage of "fix" to define recursive functions. Although I think that I understood how to use "fix", I still wonder what the advantages of "fix" are (as compared to the "conventional" approach to define recursive functions).

Any hints are appreciated.

...

So actually, I suppose it is useful for small, anonymous recursive definitions.

It also exposes the recursive computation structure for direct manipulation, enabling one to perform certain program transformations/refactorings. Search for "fixpoint fusion" and "fixed point promotion". While one might say: that's the business of a compiler, actually existing ones are not very sophisticated in that regard, so one might want to do such transformations "by hand"...

Oh, excellent point. Just as naming particular loop structures (such as 'map' or 'unfoldr') enable more precise optimisations, such as fusion, so naming recursive functions saves the compiler some work discovering the name. -- Don

Just casting my vote for the helpfulness of this reference. 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). On 7/26/07, Chung-chieh Shan wrote:

You might enjoy this paper:

Bruce J. McAdam, 1997. That about wraps it up: Using FIX to handle errors without exceptions, and other programming tricks. Tech. Rep. ECS-LFCS-97-375, Laboratory for Foundations of Computer Science, Department of Computer Science, University of Edinburgh. http://www.lfcs.informatics.ed.ac.uk/reports/97/ECS-LFCS-97-375/

-- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig It is the first responsibility of every citizen to question authority. Benjamin Franklin

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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 wrote:

On 7/26/07, Nicolas Frisby 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe