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组合子
网友评论