Post #117

定义递归函数时，一般需要在函数体中引用正在定义的函数名： fact = x => x == 0 ? 1 : x * fact(x-1) 但想不引用也很容易，用 quine 的思路，把自己作为参数传给自己就行，并且每次调用自己时也要先把自己传给自己： fact = (self => x => x == 0 ? 1 : x * self(self)(x-1))(self => x => x == 0 ? 1 : x * self(self)(x-1)) 为了避免复制粘贴相同代码，我们可以用一个函数帮我们“打结”： 令 knot = f => f(f) fact = knot(self => x => x == 0 ? 1 : x * self(self)(x-1)) 调用自己时写 self(self)(x-1) 比较丑，可以先写成 rec(x-1)，然后用一个函数帮忙“翻译”： 令 wrapper = f => self => x => f(self(self))(x) fact = knot(wrapper(rec => x => x == 0 ? 1 : x * rec(x-1))) 如果我们把先 wrapper 再 knot 合并为一步，就得到了 Z 组合子： Z = f => knot(wrapper(f)) Z = f => (self => x => f(self(self))(x))(self => x => f(self(self))(x)) 在惰性求值的语言中，x => f(self(self))(x) 可以化简为 f(self(self)) 而不会产生无限递归，这就是 Y 组合子，它在严格求值的语言中会无限递归： Y = f => (self => f(self(self)))(self => f(self(self))) Z 组合子和 Y 组合子可以求不动点，上面出现过的这个函数的不动点就是阶乘函数 fact： rec => x => x == 0 ? 1 : x * rec(x-1) 求不动点就是把函数返回的结果“时间倒流”作为参数提供给函数。想象这个函数收到的参数 rec 如果就是它的返回值本身（x => x == 0 ? 1 : x * rec(x-1)），那么一层层展开后正好就是阶乘函数： x == 0 ? 1 : x * (x-1 == 0 ? 1 : (x-1) * (x-2 == 0 ? 1 : (x-2) * (...))) 但 knot 并不是求不动点的函数，先 wrapper 再 knot 才能求不动点。 参考资料： https://lptk.github.io/programming/2019/10/15/simple-essence-y-combinator.html