Fixed Point Combinator

[Tony Davie]

Nick asked:

>http://www.deene.ufu.br/clean/monads.htm defines a way to find the factorial
>of a number using a fixed point combinator. I'm having a little bit of
>trouble with this because it's only covered sparsely in the document, and I
>have no previous experience with such combinators.
>    The combinator is defined as,
>
>Y f= f (Y f)
>
>And the factorial is defined as,
>
>Y (\ loop n m -> (if (n<1) m (loop (n-1) (n*m) )))
>
>I first stared at this in amazement wondering what the significance of loop
>was. In fact, loop isn't defined--so I didn't know what was going on.
>    I've come up with some ideas, but  I need help to fully understand this
>stuff.
>
>Certainly:
>    loop can be replaced with anything (e.g., "foo") --it needn't be
>defined.
>
>And probably:
>    the reason loop is there is that the function can't return (n - 1) (n
>*m)--it's type is Int Int or rather undefined--and a function can't return
>something of -that- type. Thus some function is used--applied to (n - 1) (n
>* m) as in loop (n - 1) (n * m).
>
>I was thinking that one could consider loop almost like a type constructor.
>For a function, it's pretty damn useless; it has no definition and is never
>used. But what exactly is the type of loop? Is it loop :: a b -> c?
>    Now, assuming loop is a function, the only reason it doesn't need to be
>defined is that it never actually gets used or applied to any arguments
>(because of laziness). If all of my above reasoning is correct, the type
>system must infer that loop is never used and thus needn't be defined. Is
>this the case?
>
>I realize that I've answered many of my own questions, but I'm hoping
>someone can tell me with certainty that I'm correct--or incorrect as the
>case may be--and provide the correct answers if I have erred..
>


What is loop? The answer is it's a parameter in that anonymous
non-recursive lambda expression (\ loop m n ...) just like the m and the n.
But its a higher order parameter which stands for the function you want to
make recursive. In general what you do is transform the recursive defn:

		fn n m ... x y = ........ fn ........
                                          ^
                                          |
				recursive call (possibly 1 of many)


into the non recursive defn:

                fn = Y(\ loop n m ... x y -> (........ loop ........))

with loop written wherever fn appears in the original.

What's happened is that all the recursion has been distilled out into the
single recursive call in the definition of Y.

Hope this helps


Tony Davie, Computer Science, St.Andrews University, North Haugh, St.Andrews
Scotland, KY16 9SS,      Tel: +44 1334 463257,          Fax: +44 1334
463278
mailto:ad@dcs.st-and.ac.uk         http://www.dcs.st-and.ac.uk/~ad/Home.html

'There is magic in the web' - Othello, Act 3, Scene 4