Y 组合子是 lambda 演算中的一个概念，是任意函数的不动点，在函数式编程中主要作用是 提供一种匿名函数的递归方式。
Y 组合子如下：
$$ λf.(λx.f(x x))(λx.f(x x)) $$
本文将尽量通俗易懂的以 实现匿名函数递归 为导向，推导出这一式子。
一、简介
1. lambda 表达式简介
这部分通过 js 函数介绍 lambda 表达式，如果已经了解 可以跳过这一部分。
了解一个新领域的最好方法是用已有知识进行类比。
我们可以把每一个 lambda 表达式解释为一个 js 函数："λ" 字符可以看作 function 声明，"."字符前为参数列表，"."字符后为函数体。
lambda 表达式不能被命名（赋值给变量），这也是为什么lambda演算需要引入 Y组合子的原因。
lambda 表达式只允许定义一个参数。
| 使用 | lamda 表达式 | javascript 箭头函数 | javascript 函数表达式 |
|---|---|---|---|
| 函数 | λx.x+1 | x=>x+1; | (function(x){return x+1;}); |
| 函数调用 | (λx.x+1)4 | (x=>x+1)(4); | (function(x){return x+1;})(4); |
2. 组合子与不动点
组合子对照 js 可以理解为：函数体内，没有使用外部变量。
不动点是函数的一个特征：对于函数 $f(x)$，如果有变量 $a$ 使得 $f(a)=a$ 成立，则称 $a$ 是函数 $f$ 上的一个不动点。
二、递归
1. 普通的递归
递归就是函数不断调用自身
一个最基本的调用自身的函数是这样的：
var f = () => f();f();//> f()//> f()//> ...
但这个函数仅仅是不断的调用自身，什么也没做。
一个正常的递归函数应该有一个状态，每次调用不断的递进状态，最终可以通过判断状态结束递归：
var f = p => judge(p) ? f(step(p)) : value;// 再加上“计算”的步骤，这样这个函数才有价值：var f = p => judge(p) ? calc(f(step(p)),p) : value;
一个具体的例子，计算阶乘的函数：
var factorial = n => n ? factorial(n-1)*n : 1;
调用：
factorial(4);//=> 24
2. 让匿名函数递归
由于不能给函数命名，我们需要把函数作为参数传入一个高阶函数。这样，在高阶函数中，就可以使用 参数名 来引用函数，相当于变相地给函数命了名。
构造一个高阶函数invokeWithSelf，它接受一个函数作为参数，并让这个函数将自身作为参数调用其自身：
var invokeWithSelf = f => f(f);
当这个函数传入自身作为参数时
invokeWithSelf(invokeWithSelf);//> (f=>f(f))(f=>f(f));//> (f=>f(f))(f=>f(f));//> ...
我们得到了一个匿名的无限递归函数，仿照上一节，我们可以把这个函数改造成可以使用的递归函数
//首先需要有一个参数来保存递归状态var func = f => p => f(f)(p);//加上状态改变和判断var func = f => p => judge(p) ? f(f)(step(p)) : value;//增加计算var func = f => p => judge(p) ? calc(f(f)(step(p)),p) : value;
具体例子，计算阶乘的函数：
var func = f => n => n ? f(f)(n-1)*n : 1;
调用：
func(func)(4);//> 24
匿名调用：
(f => n => n ? f(f)(n-1)*n : 1)(f => n => n ? f(f)(n-1)*n : 1)(4);//> 24
现在我们得到了一个匿名的递归函数，不过它只能用来计算阶乘。为了将其通用，我们希望将 函数的具体计算方式与其递归的形式剥离开来。
三、推导
1. 解耦递归逻辑与计算逻辑，得到 javascript 中的 Y 组合子
对于刚才的函数func，我们尝试一步步将它分解成 计算逻辑 和 递归逻辑 两部分
var func = (f => n => n ? f(f)(n-1)*n : 1)(f => n => n ? f(f)(n-1)*n : 1);//调用：func(4);//> 24
开始化简 func：
var func = n => { return (f => n => n ? f(f)(n-1)*n : 1)(f => n => n ? f(f)(n-1)*n : 1);} 提取重复形式 f => n => n ? f(f)(n-1)*n : 1：
var func = n => { var fa = f => n => n ? f(f)(n-1)*n : 1; return fa(fa);};//改写形式var func = n => { var fa = f => { return n => n ? f(f)(n-1)*n : 1; }; return fa(fa);}; 可以看出，其主要递归逻辑来自 f(f), 我们将这一部分解耦：
var func = n => { var fa = f => { var fb = n => f(f)(n); return n => n ? fb(n-1)*n : 1; }; return fa(fa);}; 可以看到 返回值 不再需要 fc 接收的参数 f, 将返回值表达式具名, 以便提取出 fc, 分离逻辑：
var func = n => { var fa = f => { var fb = n => f(f)(n); var fc = n => n ? fb(n-1)*n : 1; return fc; }; return fa(fa);}; fc 还在依赖 fb, 将 fb 作为参数传入 fc, 解除 fc 对 fb 的依赖：
var func = n => { var fa = f => { var fb = n => f(f)(n); var fc = fb => n => n ? fb(n-1)*n : 1; return fc(fb); }; return fa(fa);}; 可以发现 fc 是计算逻辑部分，将 fc 提取出 fa：
var func = n => { var fa = fc => f => { var fb = n => f(f)(n); return fc(fb); }; var fc = fb => n => n ? fb(n-1)*n : 1; return fa(fc)(fa(fc));}; 构造一个函数 fd, 化简返回值的形式：
var func = n => { var fa = fc => f => { var fb = n => f(f)(n); return fc(fb); }; var fc = fb => n => n ? fb(n-1)*n : 1; var fd = fa => fc => { return fa(fc)(fa(fc)); } return fd(fa)(fc);}; 将 fa 带入 fd, 得到递归逻辑部分：
var func = n => { var fc = fb => n => n ? fb(n-1)*n : 1; var fd = fc => { var fa = fc => f => { var fb = n => f(f)(n); return fc(fb); }; return fa(fc)(fa(fc)); } return fd(fc);};//化简fdvar func = n => { var fc = fb => n => n ? fb(n-1)*n : 1; var fd = fc => { var fa = f => { var fb = n => f(f)(n); return fc(fb); }; return fa(fa); } return fd(fc);};//化简fdvar func = n => { var fc = fb => n => n ? fb(n-1)*n : 1; var fd = fc => (f => fc(n => f(f)(n)))(f => fc(n => f(f)(n))); return fd(fc);}; 可以看到，两部分逻辑已经分离，可以得到 javascript 中的 Y 组合子：
var fn = fc;var Y = fd;
将参数名替换一下，得到 Y 组合子与计算逻辑 fn：
var fn = f => n => n ? f(n-1)*n : 1;var Y = y => (x => y(n => x(x)(n)))(x => y(n => x(x)(n)));
调用测试：
Y(fn)(4);//> 24
2. Y组合子与惰性求值
你可能注意到，刚才推导出的 Y 组合子形式与 其 λ 表达式的等价形式不一致
/*λ 表达式的等价形式*/Y = y => (x => y(x(x)))(x => y(x(x)));/*推导出的形式*/Y = y => (x => y(n => x(x)(n)))(x => y(n => x(x)(n)));
对比不难发现 n => x(x)(n) 应化为 x(x)，并且尝试直接使用等价形式时会发生爆栈
我们知道，上面的两种形式几乎是等价的，例如：
var print = str => console.log(str);// 在一个参数的情况下，等价于：var print = console.log;
但当它们作为函数参数时，其实有着略微不同：
//接收一个函数，但不使用它var y = xn => { console.log("run y"); return false ? xn(1) : 0;};//接收任意一个参数，返回一个函数var x = n => { console.log("run x"); return n1 => n1;};//调用，将参数直接传入y(x(1));//> "run x"//> "run y"//调用，将参数包裹在匿名函数中传入y((n1)=>x(1)(n1));//> "run y" 可以看到，在 y(x(1)) 的过程中，根本没有用到参数 x(1) 的值，但程序不在乎这一点，首先求出了 x(1) 的值；
x(1) 被“包裹”在一个匿名函数中，并没有运行。 对于函数参数的求值策略，不同的语言不相同：
在函数调用时，立即求值，称作“严格求值”(), js / c++ / c# 均使用严格求值
在函数运行时动态地求值，称作“惰性求值”(), 以 Haskell 为代表的函数式编程语言默认使用
javascript 中使用的是严格求值，而 lambda 表达式中使用的是惰性求值。
若将 n => x(x)(n) 替换为 x(x)，将导致 Y 组合子中的 x(x) 作为 y 的参数被立即求值。
x(x) 是一个无限递归的的式子，对它求值会使它不断地调用自身，最终导致堆栈溢出。 只进行左边部分的替换并不会导致无限调用：
Y = y => (x => y(n => x(x)(n)))(x => y(n => x(x)(n)));//可化为Y = y => (x => y(x(x))(x => y(n => x(x)(n)));
在计算这个式子时，会首先计算 参数 y 的值
x(x) 之前、会计算左边部分中 x 参数的值 而左边式子中 x 的值取决于右边部分的结果，右边返回值使左边的 x(x) 不再是无限递归。 四、总结
函数式编程的方法感觉着实有点烧脑，还没怎么实操过。
不过 js 真是厉害，什么编程方法都能用...
一直希望能够找到一种符合人们思考方式（至少符合我自己）的编程方法，让程序变得自然、易读、易写。不断尝试中。