Fixed Point Combinator

[Marco Kesseler]

Well, let's give it a try

>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.

Actually, 'loop' IS defined. It is the first argument of the following
anonymous function.

(\ loop n m -> (if (n<1) m (loop (n-1) (n*m) )))

Of course one might replace 'loop' by any other useful name. What does
this anonymous function mean?

- It delivers 'm' if 'n<1'
- otherwise it computes 'loop (n-1) (n*m)

If we merely look at the anonymous fucntion, we have no idea what
'loop' actually means. We only know it is an argument function that
gets 'called' with parameters 'n-1' and 'n*m'. In other words, it could
mean anything.

However, if we pass in this anonymous function as an argument to the
Y combinator, we get to know the 'value' of the 'loop' argument, because
'Y calls its argument fucntion 'f' and passes 'Y f' as the argument to it.
So 'loop' gets to have the value

Y (\ loop n m -> (if (n<1) m (loop (n-1) (n*m) )))

Note that the 'loop' argument, as well as 'n' and 'm' are local defs of
the anonymous fucntion. This means that we compute:

- m if 'n<1'
- otherwise, '(Y (\ a b c -> (if (b<1) c (a (b-1) (b*c) )))) (n-1) (n*m)'
(I replaced the argument names to avoid confusion).

Now we can start the whole reduction cycle again. Coming back to your
questions:

>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).

Yes and No. Indeed, the result type if the anonymous fucntion should be
of the same type as 'm'. '(n-1) (n*m)' is of the wrong type. That
is however not the reason for having the loop argument and calling it. See
above.

>
>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.

As will be clear by now: it is defined and used.

>But what exactly is the type of loop? Is it loop :: a b -> c?

loop has type 'a a -> a', assuming that n and m are of type a. Note that
the expression 'n*m' forces n and m to be of the same type, and that
the result of the anonymous function must have the same type as m.

>    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?

No, see above.

>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..

Hope this helps,

Marco

---------------------------------------------

Marco Kesseler
Oce-Technologies B.V.
St. Urbanusweg 43, Venlo, The Netherlands
P.O. Box 101, 5900 MA Venlo, The Netherlands
telephone +31 77 359 5158
fax       +31 77 359 5450
e-mail    mke@oce.nl