探索匿名递归函数

　　匿名递归

　　在 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;

　　var f0 = Fix(g) = (x) => g(Fix(g))(x);

　　这里的参数x被直接转发给了内部函数h(Fix(g))，因此我们可以在分析时简化。

　　var f0 = (x) => k(x), f=Fix(g);

　　虽然每次f=Fix(g)计算得到一个新的函数对象而不是复用已得到的f0，但二者的效果是相同的。

　　这里有一个等式：

　　g(Fix(g)) == Fix(g)

　　一般地，我们称值x是函数f的一个不动点，当且仅当f(x) = x。

　　那么根据上文中的两个等式，值Fix(g)是函数g的一个不动点。

　　Y-组合子

　　Y-组合子定义为：

　　Y = λf.(λx.f (x x)) (λx.f (x x))

　　注意：根据 α-变换，两个 λx 是不同的变元，互不影响。即上式与下式等价：

　　Y = λf.(λx.f (x x)) (λy.f (y y))

　　但只要表达式相同，自由变元的名字无关紧要，所以在两个不同的地方都用λx是没问题的。

　　拆分一下，方便理解：

　　h = λx.f (x x)
Y = λf.h h

　　写成 C# 是：

　　var Y = (f) => {
// 这虽然写得出代码，但执行起来会死循环
var H = (x) => f(x(x));
return H(H);
};

　　因此这里需要多一层转发函数的嵌套，使x(x)被推迟执行。推迟执行最重要的目的是在递归到头的时候不再计算从而能够退出。

　　增加一层转发函数，这对应于 λ-演算，即可以使用 η-变换。有两个做法：

　　x x展开为λv.(x x) v

　　f (x x)展开为λv.(f (x x)) v

　　第二种变换对应的 C# 是：

　　var Y = (g) => {
var H = (h) => {
var wrapped_k = (x) => {
// 每次 h(h) 都得到一个新的 wrapped_k
var new_wrapped_k = h(h);
// 在 wrapped_k 中使用了 g
// 换取真正的功能函数，而 new_wrapped_k(next(x)) 是能递归下去的
var k = g(new_wrapped_k);
return k(x);
};
return wrapped_k;
};
// 巧妙的 H(H), h(h) 组合，创建对 g 的闭包
return H(H);
};

　　简写为：

　　var Y = (g) => {
var H = (h) => (x) => g(h(h))(x);
return H(H);
};

　　Θ-组合子

　　var H = (h) => (g) => (x) => g(h(h)(g))(x);
var Θ = H(H);

　　Θ-组合子 与 Y-组合子 的唯一区别就是变量 g 在多层函数的位置，以及因此而需要的一个重复传参的步骤。

　　这两个组合子的对比同时说明了以下等式：

　　λx.λy.((f x y) y0 x0) == λy.λx.((f x y) x0 y0)

　　END