## 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, 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)

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, www.allisons.org/ll/   (or as otherwise indicated). Created with "vi (Linux)",  charset=iso-8859-1,   fetched Saturday, 18-Jan-2020 21:39:16 EST. Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.