Combinators Explained for Beginners

Combinators are small, reusable function patterns. They don’t rely on variables or external state — they only use the inputs you give them. Think of them as the “grammar rules” of functions.

Below, each combinator is explained with intuition, diagrams, and Python equivalents.

1. Identity Combinator (I)

Lecturer’s explanation:
The Identity combinator returns exactly what you give it. It’s like a mirror: no transformation, no processing — just a direct reflection. This is the simplest possible function and is often used as a placeholder or default behaviour.

Input X

→

Output X

Lambda Calculus	Python Equivalent
λx.x “Take x and return x unchanged. A pure pass‑through function.”	I = lambda x: x

2. Constant Combinator (K)

Lecturer’s explanation:
The Constant combinator takes two inputs but always returns the first. It “locks in” the first value and ignores anything that comes after. This is useful when you want to freeze a value and prevent later inputs from affecting the result.

→

←

Y (ignored)

Result:

Lambda Calculus	Python Equivalent
λxy.x “Take x, then take y, but always return x. The second input is ignored entirely.”	K = lambda x: (lambda y: x)

3. Substitution Combinator (S)

Lecturer’s explanation:
The S combinator takes two functions and one value. It applies the value to both functions and then combines the results. This pattern is fundamental in functional programming because it lets you distribute a shared input across multiple computations.

Function f

Function g

Value z

f(z) + g(z)

S combines them → f(z)(g(z))

Lambda Calculus	Python Equivalent
λxyz. x(z)(y(z)) “λxyz is shorthand for λx.λy.λz — a function that takes x, then returns a function waiting for y, then returns a function waiting for z. After receiving all three, it runs both x and y on z. Then it treats x(z) as a function and feeds it the result of y(z). This lets two computations share the same input and then combine their outputs.”	S = lambda x: (lambda y: (lambda z: x(z)(y(z))))

4. Self‑Apply Combinator (B)

Explanation:
The B combinator applies a function to itself. This is the conceptual seed of recursion — a function using its own definition. It works only when x is itself a function, because we call x using x as the argument.

Function F

→

F(F)

Lambda Calculus	Python Equivalent
λx.xx “λx means the function takes one argument called x. The body xx means ‘apply x to itself’, written as x(x). This pattern allows a function to receive its own definition as input, forming the basis of recursive behaviour.”	B = lambda x: x(x)