**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**

## 0 comments:

## Post a Comment

Let us know your responses and feedback