Lambda Calculus Fixed-Point Operator Y (lazy)

The fixed-point operator (paradoxical combinator, Y 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)

 

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 {<B> Factorial via Y </B>}

output area

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.