Combinators

• The identity combinator \(I = \lambda x. x\)
• The \(K\) combinator \(K = \lambda x y. x\)
• \(\lambda x. y\) is not a combinator, since \(y\) is free
• \(Y = \lambda x. Y x\) is not a combinator, since \(Y\) is free. Although it appears on the LHS, it is not bound by anything in the body.

We take the body of a combinator and plop it anywhere in a program where the combinator is used without change. For example, \(I z\) can be changed to \((\lambda x.x) z\). In contrast, \(Y z\) cannot be changed to \((\lambda x. Y x) z\) because \(Y\) is not defined.

The Y Combinator allows effective recursion when it is not possible to define functions with explicit recursion.