构造Y组合子

MinHeberlin 5年前
   <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>