今天花费了巨大的努力，自己推导了一遍Y-combinator。发现结果蛮简单的，就是中间遇到了几个障碍消耗了很久，作此文记录一下。

下文代码均使用scheme，不过对其要求不高，本来我对scheme知道的也不多。

引入：什么是Y-combinator

这里直接讲这玩意做什么的吧，历史上是怎么产生的我就没追溯了。

一句话来描述就是，我们可以通过这个玩意编写匿名递归函数。

先看例子吧，举个简单的递归函数：计算阶乘（好像大家都喜欢用这个例子)

1
2
3
4
5

(define fact
  (lambda (n)
    (if (equal? n 0)
        1
        (* n (fact (- n 1))))))

注意如果我们要将其写成一个匿名函数，那么我们不可能在函数里面使用fact，那么通过加一个self参数可以解决这个问题。

1
2
3
4
5
6

(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的部分)：

1
2
3
4
5
6

(define F
  (lambda (self)
    (lambda (n)
      (if (equal? n 0)
          1
          (* n (self (- n 1)))))))

然后有一个运算符Y，只要执行(Y F)，就得到了我们想要的内容。比如

1
2

(define fact (Y F))
(fact 6) ;=> this return 720

那么主要的工作就是这个Y长什么样了

Y的推导

注意到由于F的新写法，我们必须把正确的函数传进去，而不是传F自身，而正确的函数就是我们想要的(Y F)，我们从这里开始。

1
2
3

(define Y
  (lambda (F)
    (F (Y F))))

这里的Y出现了递归，我们利用上文已经实现过的匿名递归技术来解决这个难题（写起来麻烦没关系，只要这次麻烦过了，呵呵～），将这个东西的名字叫做self-Y好了，于是代码演化成下面这样：

1
2
3
4
5

(define Y
  (let ((self-Y (lambda (self)
                  (lambda (F)
                    (F ((self self) F))))))
    (self-Y self-Y)))

哦，我们居然把Y写出来了，可惜这里面还有一点小问题，仔细看一下你会发现这简直就直接死循环了啊… 问题在于这个问题是个递归的，而你想把它展开却没有边界条件…… 这就变成无限循环了。

于是有意思的地方来了，我们可以借用Lazy计算的思路，等到我要用到这个函数了，我再做这个运算，于是变成：

1
2
3
4
5
6

(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的语法特性，我们可以改成下面这样。

1
2
3
4
5
6

(define Y
  (let ((self-Y (lambda (self)
                  (lambda (F)
                    (lambda n
                      (apply (F ((self self) F)) n))))))
        (self-Y self-Y)))

使用的例子

最后给一个使用匿名的递归函数的例子， 下面的语句计算了1到7的阶乘:

1
2
3
4
5
6

(map (Y (lambda (self)
          (lambda (n)
            (if (equal? n 0)
                1
                (* n (self (- n 1)))))))
     '(1 2 3 4 5 6 7))