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组合子
