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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Gilles 'SO- stop being evil' Aug 24 '13 at 8:28
  • 1
    $\begingroup$ 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. $\endgroup$ – sdcvvc Aug 24 '13 at 9:30
  • $\begingroup$ 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' :) $\endgroup$ – Róisín Grannell Aug 24 '13 at 10:08
  • 1
    $\begingroup$ 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. $\endgroup$ – 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


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:

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:

S P1 Q1
S' S P2 Q2
S (S' S) P3 Q3
S (S' (S' S)) P4 Q4
| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.