Lukas' Notes

Home

❯

Knowledge

❯

Y Combinator

Y Combinator

Jun 09, 20251 min read

lambda-calculus

Definition

Y Combinator

The Y combinator is a specific higher-order function (a combinator) and a fixed-point combinator in lambda calculus defined as:

Y≡λf.(λx.f(xx))(λx.f(xx))

The primary purpose of it is to implement recursion in lambda calculus, a formalism that lacks built-in recursive definition capabilities.

Step

A single step already shows the underlying recursive structure of the Y combinator:

λf.(λx.f(xx))(λx.f(xx))​β​λf.(f((λx.f(xx))(λx.f(xx))))​

Graph View

  • Definition
  • Step

Backlinks

  • Combinator

Created with Quartz v4.4.0 © 2025

  • GitHub