本文参考了谈谈递归中的函数变形和推导过程。主要是用 Golang 实现高阶函数的Y组合子和Z组合子,不过考虑到 Golang 只有传值函数,所以这里的Y组合子其实也是Z组合子,只不过 z 函数更接近最初的定义。

前言

使用的 main 函数:

func main() {
	fact1 := y1(f1)
	fact2 := y2(f1)
	fact3 := y3(f2)
	fact4 := func(n int) interface{} {
		return y3(func(self CommonFunc) CommonFunc {
			return func(ps ...interface{}) interface{} {
				n, i, result := ps[0].(int), ps[1].(int), ps[2].(int)
				if i > n {
					return result
				}
				return self(n, i+1, result*i)
			}
		})(n, 1, 1)
	}
	fmt.Println(fact1(5), fact2(6))
	fmt.Println(fact3(5), fact4(6))
	fmt.Println(z(f2)(5))
}

函数变量 fact4 的定义中 y3 的参数为一个优化过的,使用尾递归的计算阶乘的函数。

正文

首先,使用了一个最常见的计算阶乘的匿名递归函数,绑定到变量f1:

var f1 = func(self func(int) int) func(int) int {
	return func(n int) int {
		if n < 1 {
			return 1
		}
		return self(n-1) * n
	}
}

其由下面的函数经柯里化并变形而来:

var f = func(n int, self interface{}) int {
	if n < 1 {
		return 1
	}
	return n * self.(func(int, interface{}) int)(n-1, self)
}

其中的 self 就是 f1 的不动点。然后是针对该函数的最初级的求Y组合子函数:

func y1(f interface{}) func(int) int {
	var g = func(h interface{}) func(int) int {
		var x = func(n int) int {
			h := h.(func(interface{}) func(int) int)
			return h(h)(n)
		}
		f := f.(func(func(int) int) func(int) int)
		return f(x)
	}
	return g(g)
}

去掉中间变量之后得到 y2,更像函数式编程了:

func y2(f interface{}) func(int) int {
	return func(g interface{}) func(int) int {
		return g.(func(interface{}) func(int) int)(g)
	}(func(h interface{}) func(int) int {
		return f.(func(func(int) int) func(int) int)(func(n int) int {
			return h.(func(interface{}) func(int) int)(h)(n)
		})
	})
}

进阶

然后就是最麻烦的部分,将上面的特定组合子函数改成泛型,因为原文使用了 JavaScript,没有类型的烦恼,可以轻易写出函数式编程。但在 Golang 就没那么容易了,这里我走了一些弯路,不过搞定 y3 之后就熟练了很多,马上写出了 z 函数。

func y3(f func(CommonFunc) CommonFunc) CommonFunc {
	return func(g interface{}) CommonFunc {
		return g.(func(interface{}) CommonFunc)(g)
	}(func(h interface{}) CommonFunc {
		return f(func(ps ...interface{}) interface{} {
			h := h.(func(interface{}) CommonFunc)
			return h(h)(ps...)
		})
	})
}

可以看到,使用了一个类型CommonFunc,我用这个来表示通用的函数,定义如下:

type CommonFunc func(...interface{}) interface{}

这个类型着实减少了很多负担,而且我也是经过很多尝试才确定了所有可以使用 CommonFunc 的位置,虽然应该还可以继续改造消去 interface{},但是再改只会变得繁琐。

当然,对应 y3 的就不能是 f1 这样的普通的递归函数了,必须修改为适应泛型的形式:

var f2 = func(self CommonFunc) CommonFunc {
	return func(ps ...interface{}) interface{} {
		n := ps[0].(int)
		if n < 1 {
			return 1
		}
		return self(n-1).(int) * n
	}
}

前言部分提到的尾递归阶乘函数也是类似的形式。

最后就是 z 函数了,实际上Z组合子也是Y组合子变形而来,本质上是一样的:

func z(f func(CommonFunc) CommonFunc) CommonFunc {
	return func(g func(interface{}) CommonFunc) CommonFunc {
		return func(x ...interface{}) interface{} {
			return f(g(g))(x...)
		}
	}(func(gp interface{}) CommonFunc {
		return func(x ...interface{}) interface{} {
			g := gp.(func(interface{}) CommonFunc)
			return f(g(g))(x...)
		}
	})
}

全部代码在 这里