Fixed Point Combinator

[Jens Peter Secher]

Dear Nick

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

loop is, as you mentioned, a variable, but it has function type. (I
assume you know that "(\x y -> e)" is a definition of an anonymous
function with two arguments.) Try to execute an application by hand to
understand what it is going on:

    fac 2 3
=>  (Y (\ loop n m -> (if (n<1) m (loop (n-1) (n*m) )))) 2 3
=>  ((\ loop n m -> (if (n<1) m (loop (n-1) (n*m) )))
         (Y (\ loop n m -> (if (n<1) m (loop (n-1) (n*m) ))))) 2 3
=>  (\ n m -> (if (n<1) m ((Y (\ loop n m ->
             (if (n<1) m (loop (n-1) (n*m) )))) (n-1) (n*m) ))) 2 3
=>  (\ m -> (if (2<1) m ((Y (\ loop n m ->
             (if (n<1) m (loop (n-1) (n*m) )))) (2-1) (2*m) ))) 3
=>  if (2<1) 3 ((Y (\ loop n m ->
                   (if (n<1) m (loop (n-1) (n*m) )))) (2-1) (2*3) )

=>  (Y (\ loop n m -> (if (n<1) m (loop (n-1) (n*m) )))) (2-1) (2*3)
...


Hope this helps. By the way, I think most of your questions are of a
general functional nature, and thus not suited for a specific mailing
list. You should post questions like these in e.g. the
comp.lang.functional newsgroup. Remember that many people get beep
from their mail box (and thus are distracted ;-) every time have a
question...



Jens Peter Secher
TOPPS, DIKU
U of Copenhagen

-- 
http://www.diku.dk/students/jpsecher    (I *hate* signatures!)