Fixed Point Combinator

[Marco Pil]

Dear Nick,


When one defines the factorial function using a fixed point combinator by

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

one had the following function in mind:

  fac :: Int Int -> Int
  fac n m = if (n<1) m
                     (fac (n-1) (n*m))


This function, though presumably faster, is also more complicated then
the following factorial function:

  fac :: Int -> Int
  fac n = if (n<1) 1
                   (n * fac (n-1))


Now the factorial (using a fixedpoint combinator) looks like:

  factorial = Y (\fac n -> if (n<1) 1 (n * fac (n-1)))

Note that I renamed the variable 'loop' to 'fac'. Perhaps this clarifies
the part that 'loop' plays.

The reduction sequence of 'factorial 3' might also be of help in understanding
the fixed point combinator 'Y', as well as the roll of 'loop'.

  factorial 3
  ->
  ((\fac n -> if (n<1) 1 (n * fac (n-1))) factorial) 3
  ->
  (\n -> if (n<1) 1 (n * factorial (n-1))) 3
  ->
  if (3<1) 1 (3 * factorial (3-1))
  ->
  3 * factorial (3-1)
  ->
  ...

In a way, the presence of 'fac' keeps the recursion going. That is why it was
called 'loop' in your version of the factorial.

The type of 'loop' is 'Int Int -> Int' in your example, just as the type of
the first version of the 'fac' function in this e-mail.
In my fixed point definition of factorial, the type of 'fac' is 'Int -> Int',
just as the type of the second version of 'fac'.


Yours Sincerly,

Marco Pil


P.S. I saw that Marco Kesseler was faster than I in responding to your mail,
     but I decided to post my answer anyway. I hope you do not mind.


==============================
 Marco Pil
 email:marcop@cs.kun.nl
 http://www.cs.kun.nl/~marcop
 tel: +31 (0) 24 36 52509
==============================