构造Y组合子
2016.12.07 17:12:37

Y组合子(Y-Combinator)是Lambda演算的一部分,也是FP编程中为人所津津乐道的一种方法。对于FP程序员来讲,估计也仍有不少人对其要么陌生、要么茫茫然。

Y组合子能够神奇地利用匿名函数/Lambda的方式来表述递归调用。Y组合子或不动点组合子的概念可以参考各类百科,这里就不再赘述。

由于最近在钻研Go语言,因此这里就用Go语言进行描述(文章最后也会列出其他几种语言的Y组合子实现)。但Y组合子的概念实现思路都是一致的,掌握了思路,用其他语言实现应该没问题。

话说回来,由于Go语言的类型语言特点,在Go中实现Y组合子很容易被函数定义绕晕了,动态语言则实现起来相对轻松一些。

接下来一步步解释Y组合子构建思路。

示例描述

在这里,我们随意选择了「The Go Programming Language」中的一个例子,作为我们的讲解案例:

func comma(s string) string {
    n := len(s)
    if n <= 3 {
        return s
    }
    return comma(s[:n-3]) + "," + s[n-3:]
}

该示例用来对1234567890这样的字符串进行自右往左每隔3个字符加一个逗号:1,234,567,890

这是构建递归调用的传统思路,一般情况下,我们的递归就是像上述代码这样实现的。可以称之为一般性递归(Natural Recursion)。

Y组合子构建

一 迈出构建Y组合子的第一步

我们可以发现,在一般性递归中,必须有个函数名,才能使用递归调用。而Y组合子的神奇之处就在于,它能够利用匿名函数/Lambda的方式来表述递归调用。

这是如何做到的?要消除函数名,关键是构建一个能够“自己调用自己”的匿名函数——这是很自然就能想到的,否则无法消除函数名。

下面,看看我们是怎么玩的。

纵使是匿名函数,我们姑且也给这个“无名”一个名字——f,因此f就变成了(伪代码):

f{
    return f(s[:n-3]) + ...
}

接下来,我们就需要确实消除这个“无名”的名,这可听起来像是什么高深莫测、难以理解的高深武功呐。别急,一步步来。

首先,我们需要添加一个真正的匿名函数作为包裹函数(伪代码):

func(f) {
    return ...
}

这里的return该返回啥呢?我们知道f是个递归,如果只返回f是不够的,那跟直接使用comma没什么区别,反而造成内层的f(s[:n-3])递归调用无法实现,因为——“无名”。

要返回一个匿名形式的递归函数,也就是要返回一个不断调用自身的函数,其形式为:

f(f)

这个很关键。所以有了这样的代码(伪代码):

func(f) {
    return f(f)
}

上述伪代码就实现了匿名函数递归调用自身的功能,外层加了个包裹函数是为了返回这个递归调用的匿名函数f(f)

不管怎么变来变去的,我们要的是comma的最初实现。包装器的返回类型必然跟comma函数的类型定义一样:

func(string) string

所以,我们定义一个baseFnType,其跟comma的类型定义一样:

type baseFnType func(string) string

由于匿名函数递归调用自身,f的参数必须接受自身,同时f最终也是返回一个baseFnType类型,这样才能跟包装器的返回类型一致:

type fnType2 func(fnType2) baseFnType

看看fnType2,参数是自己,返回是baseFnType类型——fnType2也是一个“递归类型”。

func(f fnType2) baseFnType {
    return f(f)
}

最后,如何调用这个匿名递归函数呢?

很容易,把逻辑以匿名函数的方式包装一下传递给这个匿名递归调用即可:

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:]
        }
    })

等等,为何最后有个return f(f)...?怎么会是f(f)呢?因为前面说了,递归调用的匿名函数现在是f(f)

好了,先来试试看:

fmt.Printf("%v\n", comma("1234567890"))

很神奇,真的输出了:

1,234,567,890

最关键的一步迈出去了。

二 简单才好

简化,遵循Scheme十诫之第八戒——“使用辅助函数来抽象表示方式”

看看逻辑混搭在这个函数里也是怪难受的,我们首先来分离逻辑和骨架。

首先把函数调用同逻辑处理做一定的分离:

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:]
        }
    })

然后我们需要为:

return func(s string) string {
    ...
}

里面的业务逻辑定义一个函数,然后通过这个函数,把业务逻辑“注入”进来,这样,以后不同的业务逻辑都能够通过这个函数“注入”进来,内部的骨架就不用调整了。因此,该函数也是个包装器函数。

在此之前我们需要定义一个包装器的函数类型,该类型以baseFnType为参数类型——因为我们传入包装器的参数是g(它的类型是func(s string) string),根据return func(s string) string这一行逻辑函数定义,包装器返回的也是一个baseFnType类型。因此,我们就有了:

type fnType1 func(baseFnType) baseFnType

以下是简化后的代码:

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)
        })
    }

来试试代码正确与否:

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"))

OK!输出:

1,234,567,890

接下来,我们把g定义直接放进到fn里:

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)
            })
        })
    }

嗯!这就是大名鼎鼎的Y组合子。

来测试一下:

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"))

结果OK!

甚至还可以带入不同逻辑,比如:

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."))

将输出:

ABCDEFGHIJKLMNOPQRSTUVWXYZ.

至此本文告一段落。

其他

由于动态语言没有强类型要求,因此实现的Y组合子更简单。下面分别列出Python、JavaScript、Scheme的Y组合子形式。

Python实现:

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.")

输出:

JavaScript:

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.")

输出:

Scheme:

(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"))

输出:


(0)

发表评论请先登录或注册