Personal tools

Super combinator

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
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