网上以“Y组合子”为关键字搜，结果其实挺多的，这里只是以我个人的理解再推一遍。
在日常开发中，Y组合子除了可以实现匿名递归以外好像也没有其他用，不过推导的过程倒是挺有意思，这里记录下。
另外，对相关问题感兴趣的可以看看《康托尔、哥德尔、图灵——永恒的金色对角线》这篇有意思的文章。
推导前的几个共识：
- 如何让下例函数体中不出现
console.log
const log = info => console.log(info)
// 升高一阶然后立即执行降一阶
const log = (fn => info => fn(info))(console.log)
- 如何惰性求值？
const fn = cb => {
// cb 永远不会执行
if(false) cb("Hello World!")
}
const genCb = msg1 => {
console.log("可能是个耗时的任务..")
return msg2 => console.log(`${msg1} ${msg2}`)
}
// 下例中，尽管fn中的cb永远不会被调用，但genCb还是被执行了
fn(genCb('Hello'))
// 在不改变 fn 与 genCb 的情况下，如何让genCb延迟计算呢？
// 可以试试这个方法：
// 原理是对fn的参数(需是函数)升高一阶，然后在其被执行时自调用一次再执行原来的逻辑
fn((...arg) => genCb('Hello')(...arg))
下面开始推导，以阶乘为例：
const F = x => x ? x * F(x-1) : 1
根据共识1，我们将依赖的F提前出来：
// 这里注意，提取F为参数f后，里面的F(x-1)调用也要改为递归形式f(f,x-1)
const F = (f, x) => x ? x * f(f, x-1) : 1
// 试下效果
// F(F, 5) // 120
柯里化为单参形式
// f(f, x-1)也要随之变为f(f)(x-1)
const F = f => x => x ? x * f(f)(x-1) : 1
// 再验算下
// F(F)(5) // 120
对于F(F)，根据共识1用高阶函数来表示就是：
(f => f(f))(F)
代入前面推导出的F，我们现在得到：
(f => f(f))(f => x => x ? x * f(f)(x-1) : 1)
为了看起来不那么闪眼睛，后面将(f => f(f))用A表示：
A(f => x => x ? x * f(f)(x-1) : 1)
接下来想办法从上面的式子中提取出原阶乘函数x => x ? x * f(x-1) : 1，使得其他部分一般化。对比发现，差别在于f(f)(x-1).
根据共识1，我们将f(f)提出去，作为参数传入，得到：
A(f => (g => x => x ? x * g(x-1) : 1)(f(f)))
这里有个问题，最后的f(f)作为参数会被立即求值而没经过条件判断，形成了无限递归，这里按共识2处理一下：
A(f => (g => x => x ? x * g(x-1) : 1)(n => f(f)(n)))
我们将g => x => x ? x * g(x-1) : 1部分用Fn来表示：
A(f => Fn(n => f(f)(n)))
紧接着将Fn 依据共识1往外拧，作为参数传入：
(g => A(f => g(n => f(f)(n))))(Fn)
现在将A所代表的(f => f(f))代回原函数体，得到：
(g => (f => f(f))(f => g(n => f(f)(n))))(Fn)
Y组合子就是前面这部分啦：
const Y = g => (f => f(f))(f => g(n => f(f)(n)))
验算下：
// 阶乘
Y(fac => n => n ? n * fac(n - 1) : 1)(5) // 120
// 斐波拉契
Y(fib => n => n >1 ? fib(n - 2) + fib(n - 1) : 1)(5) // 8
是不是有些绕，但还是蛮有趣的？
哎， 老乡别走呀，不喜欢Y组合子，这里有Z组合子了解下？另外，B、C、K、I、S..也可以看看
