# combinator

<logic> A function with no free variables. A term is either a constant, a variable or of the form A B denoting the application of term A (a function of one argument) to term B. Juxtaposition associates to the left in the absence of parentheses. All combinators can be defined from two basic combinators - S and K. These two and a third, I, are defined thus:

```	S f g x = f x (g x)
K x y = x
I x = x = S K K x

```
Combinatory logic is equivalent to the lambda-calculus but a lambda expression of size O(n) is equivalent to a combinatorial expression of size O(n^2).

Other combinators were added by David Turner in 1979 when he used combinators to implement SASL:

```	B f g x = f (g x)
C f g x = f x g
S' c f g x = c (f x) (g x)
B* c f g x = c (f (g x))
C' c f g x = c (f x) g

```
See fixed point combinator, curried function, supercombinators.

[FOLDOC]

Try this search on OneLook / Google

Nearby terms: colour perception theories of « colour theories of « combination « combinator » combinatory logic » communalism » communication system