Lambda Calculus Problem!
Author Message
Lambda Calculus Problem!

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

I would appreciate it if someone could give me some help on this.

Regards,

Sam

Tue, 01 Feb 2005 10:59:17 GMT
Lambda Calculus Problem!

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

> I would appreciate it if someone could give me some help
> on this.

Perhaps Felleisens "Why Y works"-lecture is of some help.

ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/Y.ps.gz

--
Jens Axel S?gaard

Tue, 01 Feb 2005 04:54:47 GMT
Lambda Calculus Problem!

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

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.

Tue, 01 Feb 2005 23:05:27 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages