combination

n 1: a collection of things that have been combined; an

assemblage of separate parts or qualities

2: an occurrence that results in things being combined [syn: {combining},

{combine}]

3: a sequence of numbers or letters that opens a combination

lock; "he forgot the combination to the safe"

4: a group of people (often temporary) having a common purpose;

"they were a winning combination"

5: an alliance of people or corporations or countries for a

special purpose (formerly to achieve some antisocial end

but now for general political or economic purposes)

6: the act of arranging elements into specified groups without

regard to order

7: the act of combining things [syn: {combining}, {compounding}]

combinator

A function with no {free variable}s. 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},

{supercombinator}s.

(1994-12-06)