<p>构造Y组合子</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/82020e3b45ede308aa6ecaf15971a329.jpg"></p>    <p>Y组合子（Y-Combinator）是Lambda演算的一部分，也是FP编程中为人所津津乐道的一种方法。对于FP程序员来讲，估计也仍有不少人对其要么陌生、要么茫茫然。</p>    <p>Y组合子能够神奇地利用匿名函数/Lambda的方式来表述递归调用。Y组合子或不动点组合子的概念可以参考各类百科，这里就不再赘述。</p>    <p>由于最近在钻研Go语言，因此这里就用Go语言进行描述（文章最后也会列出其他几种语言的Y组合子实现）。但Y组合子的概念实现思路都是一致的，掌握了思路，用其他语言实现应该没问题。</p>    <p>话说回来，由于Go语言的类型语言特点，在Go中实现Y组合子很容易被函数定义绕晕了，动态语言则实现起来相对轻松一些。</p>    <p>接下来一步步解释Y组合子构建思路。</p>    <h2>示例描述</h2>    <p>在这里，我们随意选择了「The Go Programming Language」中的一个例子，作为我们的讲解案例：</p>    <pre>  <code class="language-go">func comma(s string) string {      n := len(s)      if n <= 3 {          return s      }      return comma(s[:n-3]) + "," + s[n-3:]  }</code></pre>    <p>该示例用来对 1234567890 这样的字符串进行自右往左每隔3个字符加一个逗号： 1,234,567,890 。</p>    <p>这是构建递归调用的传统思路，一般情况下，我们的递归就是像上述代码这样实现的。可以称之为一般性递归（Natural Recursion）。</p>    <h2>Y组合子构建</h2>    <h2>一 迈出构建Y组合子的第一步</h2>    <p>我们可以发现，在一般性递归中，必须有个函数名，才能使用递归调用。而Y组合子的神奇之处就在于，它能够利用匿名函数/Lambda的方式来表述递归调用。</p>    <p>这是如何做到的？要消除函数名，关键是构建一个能够“自己调用自己”的匿名函数——这是很自然就能想到的，否则无法消除函数名。</p>    <p>下面，看看我们是怎么玩的。</p>    <p>纵使是匿名函数，我们姑且也给这个“无名”一个名字—— f ，因此 f 就变成了（伪代码）：</p>    <pre>  <code class="language-go">f{      return f(s[:n-3]) + ...  }</code></pre>    <p>接下来，我们就需要确实消除这个“无名”的名，这可听起来像是什么高深莫测、难以理解的高深武功呐。别急，一步步来。</p>    <p>首先，我们需要添加一个真正的匿名函数作为包裹函数（伪代码）：</p>    <pre>  <code class="language-go">func(f) {      return ...  }</code></pre>    <p>这里的 return 该返回啥呢？我们知道 f 是个递归，如果只返回 f 是不够的，那跟直接使用 comma 没什么区别，反而造成内层的 f(s[:n-3]) 递归调用无法实现，因为——“无名”。</p>    <p>要返回一个匿名形式的递归函数，也就是要返回一个不断调用自身的函数，其形式为：</p>    <pre>  <code class="language-go">f(f)</code></pre>    <p>这个很关键。所以有了这样的代码（伪代码）：</p>    <pre>  <code class="language-go">func(f) {      return f(f)  }</code></pre>    <p>上述伪代码就实现了匿名函数递归调用自身的功能，外层加了个包裹函数是为了返回这个递归调用的匿名函数 f(f) 。</p>    <p>不管怎么变来变去的，我们要的是 comma 的最初实现。包装器的返回类型必然跟 comma 函数的类型定义一样：</p>    <pre>  <code class="language-go">func(string) string</code></pre>    <p>所以，我们定义一个 baseFnType ，其跟 comma 的类型定义一样：</p>    <pre>  <code class="language-go">type baseFnType func(string) string</code></pre>    <p>由于匿名函数递归调用自身， f 的参数必须接受自身，同时 f 最终也是返回一个 baseFnType 类型，这样才能跟包装器的返回类型一致：</p>    <pre>  <code class="language-go">type fnType2 func(fnType2) baseFnType</code></pre>    <p>看看 fnType2 ，参数是自己，返回是 baseFnType 类型—— fnType2 也是一个“递归类型”。</p>    <pre>  <code class="language-go">func(f fnType2) baseFnType {      return f(f)  }</code></pre>    <p>最后，如何调用这个匿名递归函数呢？</p>    <p>很容易，把逻辑以匿名函数的方式包装一下传递给这个匿名递归调用即可：</p>    <pre>  <code class="language-go">comma :=      func(f fnType2) baseFnType {          return f(f)      }(func(f fnType2) baseFnType {          return func(s string) string {              n := len(s)              if n <= 3 {                  return s              }              return f(f)(s[:n-3]) + "," + s[n-3:]          }      })</code></pre>    <p>等等，为何最后有个 return f(f)... ？怎么会是 f(f) 呢？因为前面说了，递归调用的匿名函数现在是 f(f) 。</p>    <p>好了，先来试试看：</p>    <pre>  <code class="language-go">fmt.Printf("%v\n", comma("1234567890"))</code></pre>    <p>很神奇，真的输出了：</p>    <pre>  <code class="language-go">1,234,567,890</code></pre>    <p>最关键的一步迈出去了。</p>    <h2>二 简单才好</h2>    <p>简化，遵循Scheme十诫之第八戒——“使用辅助函数来抽象表示方式”</p>    <p>看看逻辑混搭在这个函数里也是怪难受的，我们首先来分离逻辑和骨架。</p>    <p>首先把函数调用同逻辑处理做一定的分离：</p>    <pre>  <code class="language-go">comma :=      func(f fnType2) baseFnType {          return f(f)      }(func(f fnType2) baseFnType {          g := func(s string) string {              return f(f)(s)          }            return func(s string) string {              n := len(s)              if n <= 3 {                  return s              }              return g(s[:n-3]) + "," + s[n-3:]          }      })</code></pre>    <p>然后我们需要为：</p>    <pre>  <code class="language-go">return func(s string) string {      ...  }</code></pre>    <p>里面的业务逻辑定义一个函数，然后通过这个函数，把业务逻辑“注入”进来，这样，以后不同的业务逻辑都能够通过这个函数“注入”进来，内部的骨架就不用调整了。因此，该函数也是个包装器函数。</p>    <p>在此之前我们需要定义一个包装器的函数类型，该类型以 baseFnType 为参数类型——因为我们传入的函数类型是 func(s string) string ，根据 return f(f)(s[:n-3]) + "," + s[n-3:] ，包装器返回的也是一个 baseFnType 类型。因此，我们就有了：</p>    <pre>  <code class="language-go">type fnType1 func(baseFnType) baseFnType</code></pre>    <p>以下是简化后的代码：</p>    <pre>  <code class="language-go">comma :=      func(fn fnType1) baseFnType {          return func(f fnType2) baseFnType {              return f(f)          }(func(f fnType2) baseFnType {              g := func(s string) string {                  return f(f)(s)              }                return fn(g)          })      }</code></pre>    <p>来试试代码正确与否：</p>    <pre>  <code class="language-go">comma :=      func(fn fnType1) baseFnType {          return func(f fnType2) baseFnType {              return f(f)          }(func(f fnType2) baseFnType {              g := func(s string) string {                  return f(f)(s)              }                return fn(g)          })      }(func(g baseFnType) baseFnType {          return func(s string) string {              n := len(s)              if n <= 3 {                  return s              }              return g(s[:n-3]) + "," + s[n-3:]          }      })    fmt.Printf("%v\n", comma("1234567890"))</code></pre>    <p>OK！输出：</p>    <pre>  <code class="language-go">1,234,567,890</code></pre>    <p>接下来，我们把 g 定义直接放进到 fn 里：</p>    <pre>  <code class="language-go">y :=      func(fn fnType1) baseFnType {          return func(f fnType2) baseFnType {              return f(f)          }(func(f fnType2) baseFnType {              return fn(func(s string) string {                  return f(f)(s)              })          })      }</code></pre>    <p>嗯！这就是大名鼎鼎的Y组合子。</p>    <p>来测试一下：</p>    <pre>  <code class="language-go">comma :=      y(func(g baseFnType) baseFnType {          return func(s string) string {              n := len(s)              if n <= 3 {                  return s              }              return g(s[:n-3]) + "," + s[n-3:]          }      })    fmt.Printf("%v\n", comma("1234567890"))</code></pre>    <p>结果OK！</p>    <p>甚至还可以带入不同逻辑，比如：</p>    <pre>  <code class="language-go">upper :=      y(func(g baseFnType) baseFnType {          return func(s string) string {              n := len(s)              if n == 0 {                  return s              }              return g(s[:n-1]) + strings.ToUpper(s[n-1:])          }      })    fmt.Printf("%v\n", upper("abcdefghijklmnopqrstuvwxyz."))</code></pre>    <p>将输出：</p>    <pre>  <code class="language-go">ABCDEFGHIJKLMNOPQRSTUVWXYZ.</code></pre>    <p>至此本文告一段落。</p>    <h2>其他</h2>    <p>由于动态语言没有强类型要求，因此实现的Y组合子更简单。下面分别列出Python、JavaScript、Scheme的Y组合子形式。</p>    <p>Python实现：</p>    <pre>  <code class="language-go">Y = lambda fn: (lambda f: f(f))(lambda f: fn(lambda s: f(f)(s)))    Y(lambda g:      lambda s:          s if len(s)==0            else g(s[:len(s)-1]) + s[len(s)-1].upper())("abcdefghijklmnopqrstuvwxyz.")</code></pre>    <p>输出：</p>    <p style="text-align: center;"><img src="https://simg.open-open.com/show/b4f8ea36291a23b132bc22a14c03dff8.png"></p>    <p>JavaScript：</p>    <pre>  <code class="language-go">const Y = function(fn) {      return (function (f) {          return f(f);      } (function (f) {          return fn(function (s) {              return f(f)(s);          });      }));  }    Y(function(g) {      return function(s) {          let n = s.length;          if (n === 0) {              return s;          }          return g(s.substring(0, n-1)) + s.substring(n-1).toUpperCase();      }  })("abcdefghijklmnopqrstuvwxyz.")</code></pre>    <p>输出：</p>    <p><img src="https://simg.open-open.com/show/f0739544db16ad5f7bdf7e086e37778e.png"></p>    <p>Scheme：</p>    <pre>  <code class="language-go">(define Y  (lambda (fn)      ((lambda (f)      (f f)) (lambda (f)              (fn (lambda (s) ((f f) s)))))))    ((Y (lambda (g)  (lambda (s)      (cond      ((null? s) '())      (else          (cons (string-upcase (car s)) (g (cdr s)))))))) '("a" "b" "c" "d" "e"))</code></pre>    <p>输出：</p>    <p><img src="https://simg.open-open.com/show/7a77b587d64015a9e89443c4d2626bd4.png"></p>    <p> </p>    <p>来自：http://www.2gua.info/post/66</p>    <p> </p>