Примеры комбинаторов

Мы разобрали три комбинатора неподвижной точки — Карри, Тьюринга и Z — и пора сказать, что вообще такое комбинатор. Комбинатор — это замкнутый λ-терм, без свободных переменных: он ничего не берёт из окружения, а только тасует и склеивает собственные аргументы. Таких термов множество, мы посмотрим наиболее часто встречаемые:

• $\mathrm{I} = \lambda x.\,x$ — тождество: отдаёт аргумент как есть.
• $\mathrm{K} = \lambda x\,y.\,x$ — константа: берёт первый аргумент, второй отбрасывает.
• $\mathrm{S} = \lambda f\,g\,x.\,f\,x\,(g\,x)$ — подстановка: раздаёт $x$ и в $f$, и в $g$, затем применяет одно к другому.
• $\mathrm{B} = \lambda f\,g\,x.\,f\,(g\,x)$ — композиция: прогоняет $x$ через $g$, потом через $f$.
• $\mathrm{C} = \lambda f\,x\,y.\,f\,y\,x$ — перестановка: меняет местами два аргумента.
• $\mathrm{W} = \lambda f\,x.\,f\,x\,x$ — удвоение: скармливает $x$ функции дважды.

На Haskell комбинаторы выглядят так:

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)