Combinators

Combinators are mathematical objects in combinatory logic consisting of functions with no free variables. They are closed lambda-terms that can be applied to arguments to produce results, providing a variable-free foundation for function application. The concept was introduced by Moses Schönfinkel and later developed by Haskell Curry, who showed that a small set of primitive combinators suffices to express any computable function. In its simplest form the basic combinators are K, S, and I. The K combinator selects the first of two arguments: K x y = x. The S combinator distributes application: S x y z = (x z) (y z). The I combinator, the identity, can be defined as I = SKK, with I x = x. Other commonly used combinators include B for composition (B x y z = x (y z)), C for flipping arguments, and W for duplication.

In the SKI calculus, all expressions can be reduced with a small set of rules, typically K x y → x and S x y z → (x z) (y z). Any lambda-term can be translated into an equivalent expression using only SKI combinators, showing that combinators capture the same notion of computation as lambda calculus. The Y combinator provides a fixed-point combinator, enabling recursion in a language that lacks explicit recursion primitives: Y f reduces to f (Y f).

Combinators have influenced the theory of computation and functional programming, particularly in point-free programming and in the design of compiler and semantic frameworks. They remain a subject of study for their elegance and foundational role in representing computation without variables.