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:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Friday, 23-Aug-2019 08:32:54 EDT.

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