今天花费了巨大的努力，自己推导了一遍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))