Y combinator
Keywords: | lambda calculus, programming, functional, recursion |
Date: |
λf.(λx.f(x x)) (λx.f(x x))
- The y combinator is a way to implement recursion in lambda calculus
- Most basic recursion representation:
loop = loop
- Consider representing "loop" in lambda calculus (the "omega combinator"):
(λx.x x) (λx.x x)
- the function
λx.x x
takes an inputx
and returnsx
as output - we apply this function to itself
- this concept of "self application" is the key to recursion
- the function
simple example:
(λx.x x) (λx.x x)
; expanded:
=> (λ(λx.x x).(λx.x x) (λx.x x)) (λx.x x)
; result:
=> (λx.x x) (λx.x x)
general example:
rec f = f(rec f)
= f(f(f( ...
a definition of "rec" in lambda calculus (y combinator):
λf.(λx.f(x x)) (λx.f(x x))
- note that the y combinator includes the same sort of "self application" or "omega combinator" included in "loop", though the y combinator is not itself recursive because it relies on the "f" input, which is the function that should be recursed
- as the "omega combinator" is applied to itself, expanded, and evaluated, it naturally calls the "f" function input each time it's evaluated, allowing for recursion