# Super combinator

### From HaskellWiki

BrettGiles (Talk | contribs) m (Categorize) |
|||

Line 4: | Line 4: | ||

Any Haskell program can be converted into super combinators using [[Lambda lifting]]. |
Any Haskell program can be converted into super combinators using [[Lambda lifting]]. |
||

+ | |||

+ | '''Question:''' Is \x y -> x+y a supercombinator? You could get this by lambda lifting \x -> x+y in some context, but as in Haskell all functions are of single argument only it's really \x -> \y -> x+y, where x is free in the inner lambda. In addition to lambda lifting, do you have to uncurry it to \(x, y) -> x+y? |
||

See also [[Constant applicative form]] |
See also [[Constant applicative form]] |

## Revision as of 00:42, 9 July 2008

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

*This definition is bewildering until you realize that a Combinator can have non-Combinator internal subexpressions. A super combinator is "internally pure" (every internal lambda is a combinator) as well as externally.*

Any Haskell program can be converted into super combinators using Lambda lifting.

**Question:** Is \x y -> x+y a supercombinator? You could get this by lambda lifting \x -> x+y in some context, but as in Haskell all functions are of single argument only it's really \x -> \y -> x+y, where x is free in the inner lambda. In addition to lambda lifting, do you have to uncurry it to \(x, y) -> x+y?

See also Constant applicative form