Named Combinators

What Is a Combinator?

A combinator is a lambda term with no free variables. Every variable in the term is bound by some enclosing λ.

Examples of combinators:

• λx.x — the variable x is bound by λx
• λx.λy.x — both x and y are bound
• λx.λy.λz.x z (y z) — all three variables are bound

Examples of non-combinators:

• λx.y — y is free
• x — x is free
• λx.x z — z is free

Because combinators have no free variables, they are self-contained. Their behavior depends only on what arguments they receive, never on an external context. This makes them portable building blocks.

The Identity Combinator

The simplest combinator is the identity, written I:

I = λx.x

Applied to any term, I returns that term unchanged:

I a = (λx.x) a →β a

We have been using this term since Topic 00. It takes one argument and returns it. No selection, no duplication, no rearrangement — just the argument, passed straight through.

The Constant Combinator

The constant combinator (or first selector), written K:

K = λx.λy.x

K takes two arguments and returns the first, discarding the second:

K a b = (λx.λy.x) a b →β a

The second argument b is substituted for y, but y does not appear in the body after the first reduction, so b vanishes. K produces a constant function: K a returns λy.a, a function that ignores its input and always returns a.

K Looks Familiar

K = λx.λy.x. Look at that definition again.

In Topic 05, we defined TRUE = λx.λy.x — a selector that takes two arguments and returns the first.

K and TRUE are the same lambda term. The combinator that makes constant functions and the boolean that selects the first alternative are literally identical. The same pattern serves two purposes depending on how we use it.

This is not a coincidence. Lambda calculus has no types, no categories, no distinction between "boolean" and "utility function." A term is what it does, and λx.λy.x does the same thing whether we call it K or TRUE.

The Substitution Combinator

The substitution combinator, written S:

S = λx.λy.λz.x z (y z)

S takes three arguments and does two things:

1. Applies x to z
2. Applies y to z
3. Applies the first result to the second

In other words, S distributes z to both x and y, then combines the results:

S f g a = f a (g a)

Think of S as a way to apply two functions to the same argument and combine their results. The third argument z is shared — it goes to both x and y.

Apply I

I = λx.x. The identity combinator returns its argument unchanged.

I a = (λx.x) a →β a

One step: substitute a for x in the body x, giving a.

Apply K

K = λx.λy.x. The constant combinator returns its first argument and discards the second.

K a b = (λx.λy.x) a b →β a

• Step 1: (λx.λy.x) a →β λy.a
• Step 2: (λy.a) b →β a

I from S and K

S distributes its third argument to both its first and second:

S f g z = f z (g z)

Let us apply S to K twice:

S K K z = K z (K z)

K takes two arguments and returns the first. So K z (K z) $\rightarrow_\beta$ z.

The result is z. No matter what z is, S K K z = z.

S K K behaves exactly like I — it is the identity function, built from S and K alone. No I required.

The Composition Combinator

The composition combinator, written B:

B = λx.λy.λz.x (y z)

B composes two functions: apply y to z first, then apply x to the result.

B f g a = f (g a)

Compare with S = λx.λy.λz.x z (y z), which gives z to both x and y. B only gives z to y, and feeds the result into x. There is no sharing — z appears once in the result.

If you know function composition from mathematics, B is exactly that: B f g = f ∘ g.

Flip and Duplicate

Two more named combinators:

C (flip) = λx.λy.λz.x z y

C takes three arguments and swaps the second and third:

C f a b = f b a

W (duplicate) = λx.λy.x y y

W takes two arguments and feeds the second to the first twice:

W f a = f a a

C rearranges arguments; W reuses one. Together with I, K, S, and B, these six combinators form the standard toolkit.