构造Y组合子
MinHeberlin
8年前
<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>