组合模式

在上一篇「切题」的文章中，咱们介绍了如何单纯通过几个简略概念实现一个自然数的概念。这也通知咱们，其实函数式编程一个最外围的内容就是用起码的概念派生性地产生更多的概念来实现性能。这个不像Java之类的对象式语言须要的原生概念十分多，而后又须要更多的派生概念解决问题。 然而，其实咱们在下面的文章中始终避而不谈，就是其实咱们应用了「递归」这个概念，这个概念是必须要的「原生」概念吗？还是一个能够用「原生」概念代替的「派生」概念。这一章，咱们就试图解决这个问题。 Lambda演算首先，咱们要回到\(\lambda\)演算的定义，就是作为一个函数式编程，至多要实现一个\(\lambda\)演算（当然还有更为简单组合子的模型，这里临时不思考）： 变量：\(x\)形象：\(\lambda x. M\)利用：\((M N)\)相当于函数式编程，最根本的就是实现这三个概念。而在Python中这三个的体现就是变量、匿名函数、匿名函数带入值。例如上面的例子中x就是变量，f =和g =前面的局部就是匿名函数/形象，f(1)和g(lambda x: x + 1, 1)就是利用： f = lambda x: x + 1f(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组合子的概念中来了。 Y组合子咱们从新看看这个问题，事实上，要解决它很容易，就是把power_of_2这个也当做变量通过lambda传入，即应该是如下模式： # 留神这里是伪代码不可执行power_of_2 = lambda f: ???? lambda x: 1 if (x == 0) else 2 * f(x - 1)其实咱们要做的一件事就是如何实现在利用中能够循环代换，能够有限地迭代本人。相似这个样子： ...