Back to notes

Y combinator

Keywords: lambda calculus, programming, functional, recursion
λ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 input x and returns x as output
    • we apply this function to itself
    • this concept of "self application" is the key to recursion

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