browse words by letter
a b c d e f g h i j k l m n o p q r s t u v w x y z
combinator

## combinator

```  1  definition  found

From  The  Free  On-line  Dictionary  of  Computing  (13  Mar  01)  [foldoc]:

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)

```