这个组合者的名字是什么？

Question

我最近开始随意阅读组合逻辑，我注意到我经常使用的高阶功能是组合器。该组合器实际上非常有用（例如，您可以使用它来定义多项式方程式上的添加），但是我从来没有给它一个不错的名称。有人认出这个组合者吗？ （忽略功能咖喱的差异）

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

在Lambda演算中，完全咖喱的实现为$ lambda h。 lambda f。 lambda g。 lambda x。 H（FX）（GX）$。换句话说，如果$ m $是这个神秘的组合者，则其定义方程为$ m ，h ，f ，g ，x = h ，（f ，x），（g ，x） $。

如果需要更多信息，或者我的问题缺乏关键信息，请发表评论，我将编辑我的问题。

Answer 1

这可能不是标准名称，而是 实施功能编程语言 在第16.2.4节中，西蒙·佩顿·琼斯（Simon Peyton Jones）称 S'. 。它被定义为优化组合器

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

以下示例来自上述部分。考虑

λx_n...λx_1.PQ

在哪里 P 和 Q 都是复杂的表达，两者都使用所有变量。消除lambda抽象会导致二次增加期限大小 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

等等 Pi 和 Qi 是一些术语。在...的帮助下 S' 这只会得到线性：

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