# Super combinator

Jump to: navigation, search

A super combinator is either a constant, or a Combinator which contains only super combinators as subexpressions.

To get a fuller idea of what a supercombinator is, it may help to use the following equivalent definition:

Any lambda expression is of the form `\x1 x2 .. xn -> E`, where E is not a lambda abstraction and n≥0. (Note that if the expression is not a lambda abstraction, n=0.) This is a supercombinator if and only if:

• the only free variables in E are x1..xn, and
• every lambda abstraction in E is a supercombinator.

So these are supercombinators:

• ```0<code> ```
• ` <code>\x y -> x + y`
• `\f -> f (\x -> x + x)`

These are not combinators, let alone supercombinators, because in each case, the variable y occurs free:

• `\x -> y`
• `\x -> y + x`

This is a combinator, but not a supercombinator, because the inner lambda abstraction is not a combinator:

• `\f g -> f (\x -> g x 2)`

A supercombinator which is not a lambda abstraction (i.e. n=0) is called a Constant applicative form.

Any Haskell program can be converted into supercombinators using Lambda lifting.