Quote:

> How might the first be rewritten using the second to remove the recursion?

> Carefully derive types for all three functions.

> fac n = if n<=1 then 1 else n * (fac (n-1))

> fpt f = g where g = f g

Unlike many around here I'm perfectly happy to

answer homework type questions.

Here goes (how to code function fac in pure untyped

lambda calculus, using church numerals):

Define a Y combinator as:

Y = \f. (\x. h (x x)) (\x. h (x x))

Then

fac = Y fact

where

fact = \f . \n. n (compose n (f (pred n))) (\f \x . f x)

pred = /* a neat little exercise */

compose = \f . \g . \x . f (g x)

Your problems will begin when you try to give types to

some of these functions, but, as they say in all the best textbooks:

that is an exercise left for the reader.

Of course, the correct answers are in Barendregt "The Lambda Calculus"

(as they always are).

David Lester.