不动点组合子(Fixed-point Combinator)是计算其他函数的一个不动点的高阶函数。不动点组合子允许定义匿名的递归函数。它们可以用非递归的lambda抽象来定义。

匿名函数在日常开发里有时能简化代码，考虑这样一个问题：如何构造一个匿名的递归函数。比如构造一个匿名函数， 用递归的方法求解阶乘。

1
2
3
4
5
6
7
# 熊人族 无所畏惧
In [1]: def f(x):
   ...:     return 1 if x == 0 else x*f(x-1)
   ...:

In [2]: f(5)
Out[2]: 120

比如这样写就是一个递归的求阶乘函数。写成匿名函数也好说：

1
2
3
4
In [1]: f = lambda x: 1 if x == 0 else x*f(x-1)

In [2]: f(5)
Out[2]: 120

这时候问题来了：递归是使用函数自身的函数定义，而在 lambda 演算中你不能定义包含了自身的函数（构造出的是匿名函数）。怎么样才能用 lambda 表达式构造一个递归函数呢？ 答案是不动点组合子。

为了避免在表达式中包含自身，可以定义一个函数g， 接受一个f作为参数， 并且返回接受x的另一个函数：g = lambda f: lambda x: 1 if x==0 else x*f(x-1)。 返回的函数接受x之后，要么返回常量1，要么返回f对x－1的x次应用。使用ISZERO谓词和lambda演算里对布尔和代数的定义，g可以使用lambda演算定义。

但是，为了使返回的函数具备递归的性质，作为参数传给g的f应该具备某种性质。设 h=g(f)，h是一个递归的求阶乘函数，因此对于传入的参数f，应该有h与f等价。 即g(f) = f。这里的f，就是函数g的不动点，它可以用 lambda 演算中的不动点组合子实现。

所幸 Haskell B. Curry 找到了不动点组合子的一种，Y组合子：

也就是说对于任意的F，Y均能找到F的不动点，这也是Y组合子力量所在，完全通用，而且这个推导简单明了。

回到前面的问题，我们构造 Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))
然后 Y(g) 就是我们需要的完美阶乘函数了，然而不行。

1
2
3
>>> Y(g)
...
RuntimeError: maximum recursion depth exceeded

原因是 call by value ，调用函数的时候，会把参数先求出来，然后调用，于是求 x(x) 就爆栈了。在 call by need 的 Haskell 里没有这问题。
我们对表达式做一个 eta 变换，Y = lambda f: (lambda x: lambda u: f(x(x))(u))(lambda x: lambda u: f(x(x))(u)) ，这样python就不会在求 Y(g) 的时候不断展开x(x)，问题得到了解决，一个很骚的阶乘函数在Y组合子的帮助下诞生了。
1
2
3
4
5
6
7
>>> Y = lambda f: (lambda x: lambda u: f(x(x))(u))(lambda x: lambda u: f(x(x))(u))
>>> g = lambda f: lambda x: 1 if x == 0 else x * f(x-1)
>>> fac = Y(g)
>>> fac(5)
120
>>> fac(10)
3628800

Y组合子还有另一种形式:

他的推导和之前的推导差不多，就不展开说了。

至此我们得到了一个 通用 的可以求lambda演算中任意函数的不动点的Y组合子，有了他之后，构造递归的匿名函数就不是什么大事了。
一般流程就是先构造 g = lambda f: (lambda ...: ...)，使得 g(f) = f 时满足需求，然后对 g 应用 Y组合子即得到最终的函数。