Lambda Calculus Fixed-Point Operator Y (lazy)

The fixed-point operator (paradoxical combinator) such that Y F = F(Y F):

let Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

in let F = lambda f. lambda n. if n=0 then 1 else n*f(n-1)

in Y F 10

{ Factorial via Y }

Note that

Y F = (λ g. F(g g)) (λ g. F(g g))

= (λ h. F(h h)) (λ g. F(g g))   --α conv. (name change)

= F ((λ g. F(g g)) (λ g. F(g g)))   --β redn (substitution)

= F (Y F)

 

NB. The applet above needs Java on.

 

And Y even applies to data structures:

let Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

in Y (lambda L. 1::L)

{ 1::1::1:: ...   via Y }

It is a good idea to print only a finite part of the result.