Super combinator: Difference between revisions
BrettGiles (talk | contribs) m (Categorize) |
No edit summary |
||
| 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]] | ||
[[Category:Glossary]] | [[Category:Glossary]] | ||
[[Category:Combinators]] | [[Category:Combinators]] | ||
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