CODEWITHSUNDEEP
lambda-calculus
dinsim
dinsim

Reputation: 2465

Iteration function in lambda calculus

I have a function like this

iter :: Int -> (a -> a) -> a -> a    
iter n f a = f (f ... (f a) .. )

how can i define such function in un-typed lambda calculus ?

any hint/help will be appreciated.

Upvotes: 1

Views: 1116

Answers (2)

Taoufik Dachraoui
Taoufik Dachraoui

Reputation: 41

iter == (rec g (fn f (fn n (fn x ((= n 0) x (g f (- n 1) (f x)))))))

Upvotes: 0

gasche
gasche

Reputation: 31459

Numbers do not exist per se in pure lambda calculus. You have to design a representation for numbers (and show that indeed those behave like numbers). The basic idea is that you can define numbers so that they are exactly the iteration function you need : n would be a lambda term that, when given a function f, compute the nth iteration of f.

This is an idea known as Church Encoding.

Upvotes: 1

Related Questions