三载前，吾尝书 Javascript 中 Y 组合子的推导 。前日，夜半欲眠，突思此物。试无凭而推，竟得。

次日，观前文，觉冗长晦涩，故作此文。

Y 组合子的目的

为了解决匿名函数的调用问题

写出一个递归函数很简单，以阶乘函数为例：

let F = x => x ? x * F(x-1) : 1;
F(5) //120

但对于匿名函数，没有变量赋值的情况下，如何解决上面的问题？
这就用到 Y 组合子。

推导

变量与参数的概念其实非常相似，我们可以用参数，替代变量赋值

(f => x => x ? x * f(x-1) : 1)

我们只要给 f 这个参数传这个函数自身，就达到了目的，首先尝试把函数直接复制一份作为参数传入：

(f => x => x ? x * f(x-1) : 1)(f => x => x ? x * f(x-1) : 1)

容易发现，如果前半部分中的f是后面这个函数:

(f => x => x ? x * f(x-1) : 1)(f => x => x ? x * f(x-1) : 1) //                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

那么f接收的参数应该是它自身，像上面f(x-1)这样的调用方式是错误的。
我们把上面的表达式改造一下：

(f => x => x ? x * f(f)(x-1) : 1)(f => x => x ? x * f(f)(x-1) : 1) //                 ^^^^                             ^^^^

上面就是我们的基本形式，可以开始化简了。

化简

首先左右两大块是一模一样的，可以用一个变量代替:

let a = f => x => x ? x * f(f)(x-1) : 1;
a(a);

还记得上面我们说的变量赋值 ↔ 参数的关系吗？我们将它改造为函数:

(a => a(a))(f => x => x ? x * f(f)(x-1) : 1)

我们的目标是分离出下面的部分：

(f => x => x ? x * f(x-1) : 1)

观察原式，只需要把下面的f(f)替换为f就能很方便的提取最后的结果了

(a => a(a))(f => x => x ? x * f(f)(x-1) : 1) //                            ^^^^

易知，对于函数f,g（我们这里讨论的全是单参数函数）

1) f 等价于 x => f(x) 2) (x => f(g(x)))(x) 等价于 (x => f(x))(g(x))

运用1)

(a => a(a))(b => (f => x => x ? x * f(f)(x-1) : 1)(b)) //         ^^^^^                                  ^^^

运用2)

(a => a(a))(b => (f => x => x ? x * f(x-1) : 1)(b(b))) //         ^^^^^                    ^          ^^^^^

运用1)和2)

(c => (a => a(a))(b => c(b(b))))(f => x => x ? x * f(x-1) : 1) //^^^                  ^        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

也就是说，前半部分就是我们要找的 Y 组合子，即

Y = c => (a => a(a))(b => c(b(b)))

重命名参数

Y = f => (x => x(x))(x => f(x(x)))

尝试调用

(f => (x => x(x))(x => f(x(x))))(f => x => x ? x * f(x - 1) : 1)(5)

然而，当我们用上面的式子调用时会爆栈：Maximum call stack size exceeded

惰性求值

下面来解决爆栈问题

还记得

f => (x => x(x))(x => f(x(x))) //                      ^^^^

是怎么来的吗？是我们从递归中?和:部分中抽离出来的，是递归条件为真的情况。递归之所以能结束，是因为函数有终止条件。而现在我们把x(x)抽离出来，相当于把递归移到了判断之前，在没有终止条件的情况下自身调用自身，最终造成了爆栈。

(a => a(a))(b => (f => x => x ? x * f(f)(x-1) : 1)(b)) //                          ^^  ^^^^^^^^^^^^^   ^ //                          判断    递归       返回 (a => a(a))(b => (f => x => x ? x * f(x-1) : 1)(b(b))) //                                             ^^^^^ //                                             递归

其实因为 js 不是惰性求值的语言，之前的等价代换不完全正确，
对于f和x => f(x)它们不是完全等价，区别是f本身如果是表达式，当以f的形式出现时，表达式会立即计算值，而如果以x => f(x)的形式出现，只有调用时才会求f的值。

运用1)的懒求值特性，把

Y = f => (x => x(x))(x => f(x(x)))

改造为:

Y = f => (x => x(x))(x => f(y => x(x)(y))) //                          ^^^^^    ^^^

这样，就得到了在 js 中可用的 Y 组合子。

Y = f => (x => x(x))(x => f(y => x(x)(y)))

尝试调用

Y(f => x => x ? x * f(x-1) : 1)(5) // 120

成功。