Wie heißt dieser Kombinator?

Question

Ich habe kürzlich angefangen, in kombinatorischer Logik beiläufig zu lesen, und ich habe festgestellt, dass eine Funktion höherer Ordnung, die ich regelmäßig verwende, ein Kombinator ist. Dieser Kombinator ist eigentlich ziemlich nützlich (Sie können es verwenden, um beispielsweise die Addition auf Polynomgleichungen zu definieren), aber ich habe ihm nie einen anständigen Namen gegeben. Erkennt jemand diesen Kombinator? (Ignorieren Unterschiede in der Funktionscurrying)

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

In Lambda Calculus wäre die voll ausgestattete Implementierung $ lambda h. lambda f. lambda g. lambda x. H (FX) (GX) $. Mit anderen Worten, wenn $ m $ dieser mysteriöse Kombinator ist, dann ist seine definierende Gleichung $ m , h , f , g , x = h , (f , x) , (g , x) $.

Wenn weitere Informationen benötigt werden oder meine Frage nicht wichtige Informationen fehlt, hinterlassen Sie bitte einen Kommentar und ich werde meine Frage bearbeiten.

Answer 1

Dies ist wahrscheinlich kein Standardname, aber in Die Implementierung funktionaler Programmiersprachen In Abschnitt 16.2.4 nennt Simon Peyton Jones es S'. Es wird als Optimierungskombinator definiert

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

Das folgende Beispiel stammt aus dem genannten Abschnitt. In Betracht ziehen

λx_n...λx_1.PQ

wo P und Q sind komplizierten Ausdruck, den beide alle Variablen verwenden. Die Eliminierung von Lambda -Abstraktionen führt zu einer quadratischen Zunahme der Termgrößen 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

usw., wo Pi und Qi sind einige Begriffe. Mit der Hilfe von S' Dies wird nur linear:

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