关于组合模式:Python函数式编程系列006Y组合子与递归

在上一篇「切题」的文章中，咱们介绍了如何单纯通过几个简略概念实现一个自然数的概念。这也通知咱们，其实函数式编程一个最外围的内容就是用起码的概念派生性地产生更多的概念来实现性能。这个不像 Java 之类的对象式语言须要的原生概念十分多，而后又须要更多的派生概念解决问题。

然而，其实咱们在下面的文章中始终避而不谈，就是其实咱们应用了「递归」这个概念，这个概念是必须要的「原生」概念吗？还是一个能够用「原生」概念代替的「派生」概念。这一章，咱们就试图解决这个问题。

首先，咱们要回到 $\lambda$演算的定义，就是作为一个函数式编程，至多要实现一个 $\lambda$演算（当然还有更为简单组合子的模型，这里临时不思考）：

变量：$x$
形象：$\lambda x. M$
利用：$(M N)$

相当于函数式编程，最根本的就是实现这三个概念。而在 Python 中这三个的体现就是变量、 匿名函数 、 匿名函数带入值 。例如上面的例子中x 就是变量，f =和 g = 前面的局部就是匿名函数 / 形象，f(1)和 g(lambda x: x + 1, 1) 就是利用：

f = lambda x: x + 1
f(1)

g = lambda h, x: h(x)
g(lambda x: x + 1, 1)

然而事实上，$\lambda$事实上是不够的，因为 $\lambda$演算只提供了一套 符号代换逻辑 ，譬如下面的f 和g的例子，事实上，咱们通过 $\lambda$演算，只能求出：

>>> f(1)
1 + 1

>>> g(lambda x: x + 1, 1)
(lambda x: x + 1)(1)
(1 + 1)

所以，第一个要减少必不可少的是化简 / 计算的逻辑，就是波及到四则运算、布尔运算的逻辑，当然这些也能够用符号 / 函数的概念派生进去，像咱们上一章做的一样。

咱们再来看对于一个递归函数还要什么，这里咱们实现一个 2 的指数 的函数：

power_of_2 = lambda x: 1 if (x == 0) else 2 * power_of_2(x - 1)

咱们首先发现，对于一个能够在现实生活中产生作用的函数而言，「分支」是必要的，它会终止不必要的无穷循环。

其实，咱们发现了一个问题，就是 power_of_2 再没有齐全实现前，就曾经调用了 power_of_2，这要求咱们的编译器须要有个特地的解决，能够疏忽这件事。并且咱们发现，下面的式子无奈用 $\lambda$ 演算来表白。这就呈现了问题。「递归」的概念是必须原生地作为程序语言的一部分，还是咱们能够用过 $$\lambda\)演算来实现。这就回到了咱们这一篇要探讨的 Y 组合子 的概念中来了。

咱们从新看看这个问题，事实上，要解决它很容易，就是把 power_of_2 这个也当做变量通过 lambda 传入，即应该是如下模式：

# 留神这里是伪代码不可执行
power_of_2 = lambda f: ???? lambda x: 1 if (x == 0) else 2 * f(x - 1)

其实咱们要做的一件事就是如何实现在利用中能够循环代换，能够有限地迭代本人。相似这个样子：

$$
f(g) = g(f(g)) = g(g(f(g))) = …
$$

或者用 $\lambda$演算的符号表白就是

$$
(\lambda x. N) g = g((\lambda x. N) g)
$$

咱们只有找到合乎这种代换的符号集 $N$即可。赫赫有名的 Haskell Curry 就找到了一个这样的答案，即 $Y = \lambda f.(\lambda x. f(x x))(\lambda x. f(x x))$。个别咱们把这个 Y 叫 Y 组合子。咱们能够验算一下下面的式子。

$$
\begin{align}
Y g && = && \lambda f.(\lambda x. f(x x))(\lambda x. f(x x)) g\\&& = && (\lambda x. g(x x))(\lambda x. g(x x)) \\&& = && g((\lambda x.g(x x))(\lambda x. g(x x))) \\&& = && g(Y g) \end {align}
$$

注：须要在这里解释一下其中的推导过程。第二行实际上将 $g$援用到了 $Y$里；第三行是将 $(\lambda x. g(x x)) $利用到了 $(\lambda x. g(x x))$里。

咱们能够依照下面的式子本人实现一个 Python 版本的Y：

Y = lambda f: (lambda g: f(g(g)))(lambda g: f(lambda y: g(g)(y)))

咱们实现 power_of_2 当初仅须要相似 def 一样的申明即可：

power_of_2 = Y(lambda f: lambda x: 1 if (x == 0) else 2 * f(x - 1))

当然，如果遇到多元函数，咱们可能须要一个 Y 组合子的推广——Z 组合子：

Z = lambda f: (lambda g: f(g(g)))(lambda g: f(lambda *y: g(g)(*y)))

比方上面这个求指数的函数power：

power = Z(lambda f: lambda x, n: 1 if (n == 0) else x * f(n - 1))
power(2, 3)

总结一下，到此为止，咱们通过 Y 组合子的形式，仅通过 $\lambda$演算的概念，实现了「递归」的概念。因而，能够论证出「递归」这个概念能够在函数式编程语言中是「派生」的，而不须要「原生」反对。咱们仅仅须要 $\lambda$演算就能模仿自然数、运算、递归这些概念了。当然，这篇文章仅仅是作为一个引子，让你看到函数式编程的表达能力以及实践根底，还有和数学特地是抽象代数、符号逻辑的分割。前面咱们将缓缓见证一个个数学概念如何转变为能够利用的例子。

Lambda 演算

Y 组合子