探索匿名递归函数|func|上下文|等式

匿名递归

在 C# 里递归可以这么定义吗？

Func fac = (x) => (x <= 1) ? 1 : x * fac(x - 1);

目前不行。因为 C# 只认识下面这种写法：

Func int> fac = null ;
fac = (x) => (x <= 1 ) ? 1 : x * fac(x - 1 );

但这实际上并未使该函数匿名化，而是把变量fac的引用绑定到了匿名函数的上下文中。这在变量fac被修改后存在失效的风险。

将自己传给自己

为了使匿名递归可行，必须将自身作为参数传给自己。

这么写可行吗？

var fac = (f, x) => (x <= 1 ) ? 1 : f(f, x - 1 );
fac(fac, 5 );

在 C# 里不行。因为 fac 的类型签名无法被自动推断，需要人工提供。

delegate int SelfFactorial(SelfFactorial f, int x);

写成泛型，提高通用性：

delegate TResult SelfApplicable TResult>(SelfApplicable TResult> self, T arg);
SelfApplicable int> fac = (f, x) => (x <= 1 ) ? 1 : f(f, x - 1 );
fac(fac, 5 );

更进一步，为 fac 构建函数闭包，得到我们想要的函数形式：

Func Fac = (x) => fac(fac, x);

综合以上过程，给出一个通用形式的帮助函数，简化类型推断：

static Func Make(SelfApplicable self)
{
return (x) => self(self, x);
}

var fac = Make ((f, x) => (x <= 1) ? 1 : x * f(f, x - 1));

推广到两个参数的情形：

delegate TR SelfApplicable(SelfApplicable self, T1 arg1, T2 arg2);

static Func Make(SelfApplicable self)
{
return (x, y) => self( self, x, y);
}

var gcd = Make< int, int, int>((f, x, y) => (y == 0) ? x : f(f, y, x % y));

但类型推断并不是什么大问题，下文如因类型推断而无法写出，大可手动补上。

柯里化

柯里化即将多参数的函数转化为多个单参数函数的嵌套。

你可能会想到这种写法：

var fac = Make2 ((f) => (x) => (x <= 1) ? 1 : x * f(x - 1));

这需要配套怎样的Make2呢？

static Func Make2(Func, Func> g)
{
// 建立一个新的上下文，在里面用上 g 就能把 g 保存起来。
var wrapped_k = (x) => {
// 先跳过这行分析下面的，因为 h 是为了传给 g 做参数的。
// 这个操作必须在子函数体内，不然就死循环了。
var h = Make2(g);
// k 才是想要的那个功能函数，但获得这个 k 之前没法传给 g 做其参数 f，陷入了鸡生蛋蛋生鸡的矛盾。
// g 的参数 f 无法是 k，但 Make2 能构造 k 的转发函数，且转发函数使用时才会计算，不会死循环。
var k = g(h);
k(x);
};
// 这是一个 k 的转发函数，用起来就跟 k 没什么区别。而且它的上下文里有 g 的引用。
return wrapped_k;
}

这是一个不动点组合子（将在下文中解释其含义），让我们先将其重命名为Fix。

static Func Fix(Func, Func> g)
{
return (x) => g(Fix(g))(x);
}

Fix要配合一种两层的匿名函数写法。其中递归函数自身作为外层函数的参数，Fix将其转化为了可以直接使用的函数对象。

两个参数的Fix函数也可以顺利写出来了：

static Func Fix(Func, Func> g)
{
return (x, y) => g(Fix(g))(x, y);
}

// g0 也可称为单步函数
var g0 = (f) => (x) => (x <= 1) ? 1 : x * f(x - 1);
var fac = Fix(g0);
fac( 5);

var g1 = (f) => (x, y) => (y == 0) ? x : f(y, x % y);
var gcd = Fix(g1);
gcd( 10, 15);

先把单步函数抽象一下：

// use(x) 产生当次执行的计算结果
// next(f, x) 递归地产生 f(x)，或是在没有下一个 x 时及时终止
// reduce(a, b) 将当次与递归的结果合并为最终结果
var g = (f) => (x) => reduce(use(x), next(f, x));

以一个参数的Fix函数为例分析其过程。

先分析这个两层匿名函数g，并将内层函数单独称为 k：

// 注意：这是方便理解而拆开的伪代码，因为不可能使 k 在没有 f 的上下文中绑定到 f。类型推断也是个问题。
var k = (x) => reduce(use(x), next(f, x));
var g = (f) => k;