## Lambda Calculus Fixed-Point Operator Y (lazy)

 LA home Computing FP  λ-calc.   Intro   Syntax   Examples    Ints    Bools    Lists(1)    arithmetic    Y (lazy)    Y (strict)    Lists(2)    Trees    Primes(1)    Fibonacci(1)    Unique    Hamming#s    Composites    Fibonacci(2)    Thue seqs.    Edit-dist.    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.
www:
 The C++ Cookbook mastering the language

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Monday, 09-Dec-2013 05:01:23 EST.

 free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.