Combinator

lambda-calculus

Definition

Combinator

A lambda expression is called combinator if it contains no free variables.

Common

Identity

Definition

Identity Combinator

The identity combinator is defined as:

$$\mathbf{I}\equiv \lambda x.x$$

Link to original

Y Combinator

Definition

Y Combinator

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

$$\mathbf{Y}\equiv \lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$$

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

Link to original