On 7/26/07, Nicolas Frisby
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