Y组合子

Y组合子要解决的问题是如何用纯正的lambda表达式实现递归
以阶乘为例，可以采用下面的代码以递归的形式表达：

f n = if n > 1 then n * f (n-1) else 1

要求一个自然数n的阶乘只要调用f n即可
上述代码包含了一个赋值语句，而纯正的lambda表达式是没有赋值语句的，那么用纯正的lambda表达式能否实现递归呢？

可以猜测能求阶乘的函数有很多个,比如f n = foldl (*) [1..n]就是其中之一.于是我们将能求阶乘的函数f当成一个变量,这样定义阶乘就变成了求f的值

定义

g f = \n -> if n > 1 then n * f (n-1) else 1

先给出结论: f能求阶乘的充分必要条件是g f == f(==表示等效,下同)

下面不严谨地证明一下:

• 必要性
  假设f能计算阶乘,那么将g应用于f可得一个新的函数g f, 即\n -> if n > 1 then n * f (n-1) else 1, ,f能计算阶乘,由阶乘的定义, g f必然也能计算阶乘,也就是g f == f

• 充分性
  如果g f == f, 那么通过代换可以得到f == \n -> if n > 1 then n * f (n-1) else 1,这就是我们在上面给出的阶乘的递归定义形式,可以确定这样的f是能计算出阶乘的,通过数学归纳法可以证明

综上, 可以知道g f == f是f能计算阶乘的充分必要条件

那么问题就变成了"求方程g f == f的解"

很显然f应该是一个关于g的函数,那么Y组合子其实就是这个函数: f == Y g

但是具体怎么求这个解就太难了,作为民科的我只能利用前辈们留下的结论自己慢慢凑

f应该是gen gen这样的形式,gen满足

gen = \x -> g (x x)

于是gen gen = g gen gen

这样就找到了g的不动点

现在我们开始构造Y组合子：
由上面的讨论可以知道Y g == f == gen gen == g gen gen
则

Y g = g gen gen

即

Y g = gen gen

即

Y g = (\x -> g (x x)) (\x -> g (x x))

由此便得到了Y组合子