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.
(Your fpt is the Y-operator)

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



Tue, 01 Feb 2005 23:05:27 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Lambda Calculus Question

2. lambda calculus implementation

3. Introduction to lambda calculus ?

4. Negativism and division in lambda-calculus

5. Lambda calculus + Church numerals

6. Typed lambda calculus, recursion and halting

7. lambda calculus: delta rules

8. Need help on Lambda calculus reduction please.

9. Q: reduction strategies in lambda calculus

10. Lambda-Calculus

11. Introduction to Lambda Calculus

12. Typed Lambda calculus

 

 
Powered by phpBB® Forum Software