Quel est le nom de ce combinateur?

Question

Je l'ai récemment commencé à lire avec désinvolture dans la logique combinatoire, et je remarque qu'une fonction d'ordre supérieur que je utilise régulièrement un combinateur. Ce combinateur est en fait assez utile (vous pouvez l'utiliser pour définir plus sur des équations polynomiales, par exemple), mais je ne lui a donné un nom décent. Est-ce que quelqu'un reconnaît ce combinateur? (Sans tenir compte des différences de fonction corroyage)

unknown = function (h, f, g)
    function (x) h( f(x), g(x) )
}

Dans le calcul lambda, la mise en œuvre pleinement cari serait $ \ Lambda h. \ Lambda f. \ Lambda g. \ Lambda x. h (f x) (g x) $. En d'autres termes, si $ M $ est ce combinateur mystère, alors son équation définissant est M $ \, h \, f \, g \, x = h \ (f \, x) \, (g \, x) $.

Si plus d'information est nécessaire, ou ma question manque des informations clés s'il vous plaît laisser un commentaire et je vais modifier ma question.

Answer 1

Ceci est probablement pas un nom standard, mais dans La mise en œuvre de la programmation fonctionnelle Langues dans la section 16.2.4 Simon Peyton Jones appelle S'. Il est défini comme un combinateur d'optimisation

S (B x y) z = S' x y z

L'exemple suivant est de la section mentionnée. Considérez

λx_n...λx_1.PQ

où P et Q sont l'expression compliquée que les deux utiliser toutes les variables. L'élimination des abstractions lambda conduit à une augmentation quadratique des tailles de terme 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., Où Pi et Qi quelques termes. Avec l'aide de S' cela devient seulement linéaire:

P Q
S P1 Q1
S' S P2 Q2
S (S' S) P3 Q3
S (S' (S' S)) P4 Q4