浅谈Y组合子
这篇文章希望能够通俗地讲清楚Y组合子，如果对lambda演算感兴趣的同学可以看看最后的相关资料
在lambda中，如果我们想要递归，以斐波那契数列为例，可以这样：
let power = lambda n. IF_Else n==0 1 n*power(n-1) 然而，在”纯”lambda演算中，是没有let关键字的。我们需要换个方法，如果直接的不行，那么我们可以尝试间接的。很容易能想到通过参数把自己传给自己：
let P = lambda self n. If_Else n==0 1 n*self(self, n-1) P(P, 3) 这么做就显得很不优雅，我们要想一个办法，能够通用的把自己传给自己。就像上面一样。我们试着构造一下，把斐波那契数列的逻辑替换为任意函数：
let gen = lambda self. AnyFunction(self(self)) gen(gen) 尝试写出斐波那契数列的AnyFunction实现：
let AnyFunction = lambda self n. If_Else n==0 1 n*self(n-1) 经过展开之后，发现任何函数只要在AnyFunction那个位置，经过上面的代码之后，都能够实现递归。
其中gen(gen)展开如下：
gen(gen) => AnyFunction(gen(gen)) 可能你会疑问，gen(gen)为什么能够表达自己呢？因为gen(gen)=>AnyFunction(gen(gen))，它能够返回AnyFunction自身，这就得到自己了。并且这时会把这个gen(gen)再传给AnyFunction。而gen(gen)不到求值的时候都不展开，因此gen(gen)没有被调用时，没有任何作用，但是一旦AnyFunction内部调用了传进来的自身，那么就进行求值得到。通俗来讲， 与其说gen(gen)是自身，还不如说这是一个把能够得到自己，并且把gen(gen)再次传入的函数。
在理解这个机制之后，通用的递归函数已经到手。封装一下就轻而易举了，这就是传说中的Y组合子：
let Y = lambda f. let gen = lambda self. f(self(self)) gen(gen) 再把let去掉可得到Y的定义：
lambda f. (lambda x. (f(x x)) lambda x. (f(x x))) 接下来可以试着使用一下：
( ( lambda f. (lambda x. (f(x x)) lambda x. (f(x x))) ) ( lambda f. lambda n. n==0 ? 1 : n*(f n-1) ) ) 4 看，完美！证明了lambda只需要alpha/beta/eta三条规则而不需要命名。
相关资料，从易到难排序
- g9的lambda calculus系列
有很多lambda的入门讲解，幽默风趣 - The Little Schemer
手把手学lambda - The Seasoned Schemer
手把手2 - SICP
不用多说，看书评 - MIT讲SICP
MIT的课，值得一看
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
