函数式编程中的 Y 组合子

Question

Y 组合子是 Lambda 演算的一部分，什么你问我什么是 Lambda 演算，其实我也不知道，什么又是 Y 组合子，它在学术上的定义我也不知道，它在生产上实际生产过程中毫无用处，但是用代码将其推导出来却是一件很舒服的事。

来考虑这样一个问题：实现一个匿名的递归累加函数…

一类函数

在解决上面的问题之前，我们先来了解两个概念，一类函数和函数的递归调用。

一类函数即函数可以当做变量，参数使用，函数本身是一种对象。很多语言都有这种特性，比如我们熟悉的 JavaScript，Python 等等。

// 面向过程编程
// 求数组的累加结果
const sum = function(arr) {
    let result = 0;
    for (let i = 0; i < arr.length; i++) {
        result += arr[i];
    }
    return result;
};
console.log(sum([1, 2, 3, 4, 5]));

由于有了一类函数的存在，我们可以使用函数式编程的方式处理需求。

// 函数式编程
// 求数组的累加结果
const sum = arr => arr.reduce((acc, n) => acc + n, 0);
console.log(sum([1, 2, 3, 4, 5]));

上述实现中我们给 reduce 的第一个参数是一个函数， reduce 方法中将其应用到了数组的每个元素上。在 JavaScript 中，我们可以这样做，正是因为这里的函数是一类函数，而如果在 C、C++或者 Java（Lambda 表达式也可以实现类似效果，但是 Java 中的函数毕竟不是一类函数）中我们却不能这样做。

下面我们来看另一个概念，函数的递归调用。

函数的递归调用

同学们对于递归函数一定不陌生，我们实际学习工作过程中肯定也有这样的需求，比如一个斐波那契数列，比如树的深度优先遍历。

我们先来看一个简单的累加函数，给定一个 n ，求 1 到 n 的累加结果（我们当然可以通过 for 或者 while 循环实现，但这里我们规定用函数递归调用实现）。

const f = n => n < 2 ? 1 : n + sum(n - 1);

这里在 f 函数中调用了自身，并通过参数去控制结束递归调用的终止条件，这就一个基本的递归调用。

匿名函数的递归调用

好了，介绍了两个非常基本的概念（有点无聊对不对，接下来就不无聊了，做好心理准备）。

从上面的例子可以看出，递归函数的一个关键点就在于调用自身，而调用自身必须要知自身的函数名，这样才能通过作用域链访问到函数对自己的声明和定义。

回到一开始提出的问题：如何实现一个匿名的递归累加函数？

首先可以想到的是，函数体内我们没有办法把 sum 函数隐藏掉，但是函数外面也不能在用 f 函数去定义它，为了将函数名隐藏，我们可以考虑使用函数参数的形式。

s => n => n < 2 ? 1 : n + s(n - 1);

上面是一个匿名函数，但是它没有被调用，而且这里我们已经假定了 s 是一个实现了递归的累加函数，却没有任何地方将其传进去。

我们需要让 s 是一个已经实现了的递归累加函数，等等，我们不是已经有这样一个函数了吗？这个式子自己就有点像，我们把它当做参数，传入自己会怎么样呢？

接下来我们做如下修改。

(s => n => n < 2 ? 1 : n + s(n - 1))(s => n => n < 2 ? 1 : n + s(n - 1));

遗憾的是，上面的式子是错误的！注意我们在上面假定 s 是一个累加函数，但是修改后的 s 并非一个累加函数， s 调用之后的返回值才是，怎么回去它的返回值呢？

调用一下就行了。

(f => n => n < 2 ? 1 : n + f(f)(n - 1))(f => n => n < 2 ? 1 : n + f(f)(n - 1));

为什么要传一个 f 给 f 呢？因为只有这样，在一层层的递归调用中，我们才能通过 f(f) 获得其返回结果。

这里将改用 f ，是为了和 s 进行区分， s 表示的是递归累加函数，而这里的 f 并不是， f(f) 才是。

好了，我们已经实现了一个完美的自调用的匿名函数，它可以实现一个累加的功能，不信你可以把下面的代码拿到浏览器控制台去运行一遍。

(f => n => n < 2 ? 1 : n + f(f)(n - 1))(f => n => n < 2 ? 1 : n + f(f)(n - 1))(5);
// 15

是不是很神奇？

为了让我们的函数更好看一点，我们可以进一步简化一下。

注意这个表达式的左右两部分是完全一样的，也就是说它是一个函数自己在调用自己，自己是自己的唯一参数。

(f => f(f))(f => n => n < 2 ? 1 : n + f(f)(n - 1));

这种形式还不够优雅，因为我们的累加逻辑还是耦合在这个自调用的函数之中，能不能把累加逻辑提取出来呢？

继续变形。

(f => f(f))(f => (s => n => n < 2 ? 1 : n + s(n - 1))(f(f)));

事实上我们不希望 f(f) 立刻被执行，因为没有参数进来时， f(f) 在匿名函数定义的时候就会立刻被执行，这样直接就会超出调用栈，这里做个小处理。

(f => f(f))(f => (s => n => n < 2 ? 1 : n + s(n - 1))((...a) => f(f)(...a)));

注意上式中的 s => n => n < 2 ? 1 : n + s(n - 1) ，这就是本小节中的第一个式子，它是不是一个优雅的匿名累加递归函数呢？

我们将其再次提取出来。

(t => (f => f(f))(f => t((...a) => f(f)(...a))))(s => n => n < 2 ? 1 : n + s(n - 1));

t 表示我们要进行处理的匿名递归函数。

现在已经得到了一个完美的式子，可以看出，上式的右侧是一个匿名累加函数，将其交给左侧的式子处理之后，它就成了一个可以递归调用自身的匿名累加函数。

Y 组合子

现在我们来看下式子的左半边。

t => (f => f(f))(f => t((...a) => f(f)(...a)))

它将一个递归函数完美地转换成了匿名的形式，函数以参数的形式传入，完全不依赖变量声明。

有的同学可能还没有意识到它的神奇。

我们换个问题：实现一个匿名的递归累乘函数……

(t => (f => f(f))(f => t((...a) => f(f)(...a))))(mul => n => n < 2 ? 1 : n * mul(n - 1));

再换个问题，实现一个匿名的递归斐波那契数列，对于传入的参数 n，求斐波那契数列值中的第 n 个值。

(t => (f => f(f))(f => t((...a) => f(f)(...a))))(fib => n => n < 3 ? 1 : fib(n - 1) + fib(n - 2));

看到这个式子的神奇之处了吗？它能将任何形式的函数递归调用转换为匿名函数递归调用。

这个式子就被成为 Y 组合子，它的作用就是实现匿名函数的递归自调用，上一小节的推导过程就是 Y 组合子的推导过程（并不太严谨，但是大体过程有了）。

事实上，函数式编程语言都能实现 Y 组合子。

// JavaScript 版本的 Y 组合子
const Y = t => (f => f(f))(f => t((...a) => f(f)(...a)));

# Python 版本的 Y 组合子
Y = lambda t: (lambda f: f(f))(lambda f: t(lambda *a: f(f)(*a)))

# Julia 版本的 Y 组合子
Y = t -> (f -> f(f))(f -> t((a...) -> f(f)(a...)))

总结

让我来猜一下同学们看这篇文章的感受吧。

我相信对于绝大多数人来说，一开始的时候 Y 组合子并不好理解，如果同学们感兴趣的话，这个过程建议手动去推一推，上面的每一个步骤都可以仔细去看一看，这样更容易加深每一步的理解。

当然，不理解它也没有什么影响，Y 组合子在实际生产过程中确实没什么用，毕竟什么情况下一个递归函数会非要匿名呢？至少我从来没遇到过。

参考

1. 重新发明 Y 组合子 JavaScript(ES6) 版 - 王霄池
2. 函数式编程的 Y Combinator 有哪些实用价值？ - 温悦