Examples of combinators

We have gone through three fixed-point combinators — Curry’s, Turing’s and Z — and it is time to say what a combinator is in general. A combinator is a closed λ-term, one with no free variables: it takes nothing from its surroundings and only shuffles and glues together its own arguments. There are plenty of them; we will look at the most common:

• $\mathrm{I}$ $= \lambda x.\,x$ — identity: returns its argument as is.
• $\mathrm{K}$ $= \lambda x\,y.\,x$ — constant: takes the first argument and discards the second.
• $\mathrm{S}$ $= \lambda f\,g\,x.\,f\,x\,(g\,x)$ — substitution: hands $x$ to both $f$ and $g$, then applies one to the other.
• $\mathrm{B}$ $= \lambda f\,g\,x.\,f\,(g\,x)$ — composition: runs $x$ through $g$, then through $f$.
• $\mathrm{C}$ $= \lambda f\,x\,y.\,f\,y\,x$ — flip: swaps the two arguments.
• $\mathrm{W}$ $= \lambda f\,x.\,f\,x\,x$ — duplication: feeds $x$ to the function twice.

In Haskell the combinators look like this:

id 5             -- => 5            (I)
const 1 2        -- => 1            (K)
ap (+) (*2) 3    -- => 9  = 3 + 3*2 (S)
((+1) . (*2)) 3  -- => 7  = 3*2 + 1 (B)
flip (-) 3 10    -- => 7  = 10 - 3  (C)
join (*) 4       -- => 16 = 4*4     (W)