2
$\begingroup$

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.

$\endgroup$
4
  • 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$ Aug 24, 2013 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, 2013 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$ Aug 24, 2013 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$ Aug 25, 2013 at 18:07

1 Answer 1

4
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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