Difference between revisions of "Super combinator"
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