# What is the name of this combinator?

I've recently started casually reading into combinatorial logic, and I noticed that a higher-order function that I regularly use is a combinator. This combinator is actually pretty useful (you can use it to define addition on polynomial equations, for example), but I never gave it a decent name. Does anyone recognise this combinator? (ignoring differences in function currying)

unknown = function (h, f, g)
function (x) h( f(x), g(x) )
}


In lambda calculus, the fully curried implementation would be $\lambda h. \lambda f. \lambda g. \lambda x. h (f x) (g x)$. In other words, if $M$ is this mystery combinator, then its defining equation is $M \, h \, f \, g \, x = h \, (f \, x) \, (g \, x)$.

• In terms of common combinators, $M h f g = S (B h f) g$ ($B$ is the function composition combinator). I don't know if this has a name, there are lots of combinators out there. – Gilles 'SO- stop being evil' Aug 24 '13 at 8:28
• In Haskell, it is known as liftM2. This function lifts a -> b -> c to m a -> m b -> m c, where m is any monad (such as r -> in this case) and is extremely useful in many places. – sdcvvc Aug 24 '13 at 9:30
• liftM2 is a valid name, so if you promote this comment to an answer I'll accept it. Funny, my stopgap name was very close; I called the combinator 'binarylift' :) – Róisín Grannell Aug 24 '13 at 10:08
• This isn't exactly 'professional', but Smullyan's name for this in To Mock A Mockingbird is the Phoenix, $\Phi xyzw=x(yw)(zw)$, and he derives it as $\Phi = B(BS)B$; searching on 'Phi combinator' doesn't seem to turn up anything useful, though, so I suspect that name is non-standard. – Steven Stadnicki Aug 25 '13 at 18:07

This isn't probably a standard name, but in The Implementation of Functional Programming Languages in Section 16.2.4 Simon Peyton Jones calls it S'. It is defined as an optimization combinator

S (B x y) z = S' x y z


The following example is from the mentioned section. Consider

λx_n...λx_1.PQ


where P and Q are complicated expression that both use all the variables. Eliminating lambda abstractions leads to quadratic increase of term sizes in n:

P Q
S P1 Q1
S (B S P2) Q2
S (B S (B (B S) P3)) Q3
S (B S (B (B S) (B (B (B S)) P4))) Q4


etc., where Pi and Qi are some terms. With the help of S' this gets only linear:

P Q
S P1 Q1
S' S P2 Q2
S (S' S) P3 Q3
S (S' (S' S)) P4 Q4