[Solved]: What is the name of this combinator?

Problem Detail: 

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.

Asked By : RyanGrannell

Answered By : Petr Pudlák

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 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13901

3.2K people like this

 Download Related Notes/Documents