今天花费了巨大的努力,自己推导了一遍Y-combinator
。发现结果蛮简单的,就是中间遇到了几个障碍消耗了很久,作此文记录一下。
下文代码均使用scheme
,不过对其要求不高,本来我对scheme
知道的也不多。
引入:什么是Y-combinator
这里直接讲这玩意做什么的吧,历史上是怎么产生的我就没追溯了。
一句话来描述就是,我们可以通过这个玩意编写匿名递归函数。
先看例子吧,举个简单的递归函数:计算阶乘(好像大家都喜欢用这个例子)
(define fact
(lambda (n)
(if (equal? n 0)
1
(* n (fact (- n 1))))))
注意如果我们要将其写成一个匿名函数,那么我们不可能在函数里面使用fact
,那么通过加一个self
参数可以解决这个问题。
(define fact
(lambda (self)
(lambda (n)
(if (equal? n 0)
1
(* n (self (- n 1)))))))
这样调用的时候写成: ((fact fact) 6)
,可惜这样写是错的…., 因为上面最后一行需要写成 (* n ((self self) (- n 1)))))))
这样就编写出来了可以匿名递归的函数,但是有一个麻烦的地方是你程序里面要写成(self self)
,别人调用的时候也要写两遍函数名,这样就还有改进的空间。下面开始改进,我们用F表示这个函数,我们自己希望写成(不包括define F
的部分):
(define F
(lambda (self)
(lambda (n)
(if (equal? n 0)
1
(* n (self (- n 1)))))))
然后有一个运算符Y
,只要执行(Y F)
,就得到了我们想要的内容。比如
(define fact (Y F))
(fact 6) ;=> this return 720
那么主要的工作就是这个Y
长什么样了
Y的推导
注意到由于F
的新写法,我们必须把正确的函数传进去,而不是传F
自身,而正确的函数就是我们想要的(Y F)
,我们从这里开始。
(define Y
(lambda (F)
(F (Y F))))
这里的Y
出现了递归,我们利用上文已经实现过的匿名递归技术来解决这个难题(写起来麻烦没关系,只要这次麻烦过了,呵呵~),将这个东西的名字叫做self-Y
好了,于是代码演化成下面这样:
(define Y
(let ((self-Y (lambda (self)
(lambda (F)
(F ((self self) F))))))
(self-Y self-Y)))
哦,我们居然把Y
写出来了,可惜这里面还有一点小问题,仔细看一下你会发现这简直就直接死循环了啊…
问题在于这个问题是个递归的,而你想把它展开却没有边界条件…… 这就变成无限循环了。
于是有意思的地方来了,我们可以借用Lazy计算的思路,等到我要用到这个函数了,我再做这个运算,于是变成:
(define Y
(let ((self-Y (lambda (self)
(lambda (F)
(lambda (n)
((F ((self self) F)) n))))))
(self-Y self-Y)))
这样只有当我们给出了F
的参数之后,相应的展开工作才会进行,我们的fact
函数可以完美运作了。
至此,我们就成功的推导出来了Y
的实现。可喜可贺,可喜可贺。当然,对于我来说,只支持一个参数的F
函数当然不够满意,利用scheme
的语法特性,我们可以改成下面这样。
(define Y
(let ((self-Y (lambda (self)
(lambda (F)
(lambda n
(apply (F ((self self) F)) n))))))
(self-Y self-Y)))
使用的例子
最后给一个使用匿名的递归函数的例子, 下面的语句计算了1到7的阶乘:
(map (Y (lambda (self)
(lambda (n)
(if (equal? n 0)
1
(* n (self (- n 1)))))))
'(1 2 3 4 5 6 7))