What is the difference between combinator and supercombinator?

Question

What is the difference between combinator and supercombinator? Both of them do not contain any free variables. That is the one thing, that I know.

• Ruud Helderman: Explanation and an example of a combinator that is not a supercombinator can be found here: wiki.haskell.org/Super_combinator

Answer 1

A supercombinator is either a constant, or a combinator which contains only supercombinators as subexpressions.

Or more completely,

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.

A combinator does not contain any free variable, but might have a subexpression that does. For example, from Haskell Wiki: Super combinator

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

the outer lambda function is indeed a combinator because it has no free variables, however its subexpression \x -> g x 2 has a free variable (g), so it is not a combinator. It follows that \f g -> f (\x -> g x 2) cannot be a supercombinator

• Fyodor Soikin: To be fair, that definition at the top is written in such a way that the only possible super combinator is a constant. For example, \x -> x cannot be a super combinator, because (1) it is not a constant, and (2) it contains a subexpression x, which is not a super combinator.
• Lorenzo: @FyodorSoikin The definition is from the Haskell Wiki and I only took the simple bit because I thought it was obvious what it meant, but I'll update it now