What is the name of this combinator?

Question

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)$.

If more information is needed, or my question is lacking key information please leave a comment and I will edit my question.

• Gilles 'SO- stop being evil': 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.
• sdcvvc: 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.
• Róisín Grannell: 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' :)
• Steven Stadnicki: 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.

Answer 1

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