每日一博 | 探索匿名递归函数
匿名递归
在 C# 里递归可以这么定义吗？
Func<int, int> fac = (x) => (x <= 1) ? 1 : x * fac(x - 1);
目前不行。因为 C# 只认识下面这种写法：
Func<int, 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<T, TResult>(SelfApplicable<T, TResult> self, T arg);
SelfApplicable<int, int> fac = (f, x) => (x <= 1) ? 1 : f(f, x - 1);
fac(fac, 5);
更进一步，为 fac 构建函数闭包，得到我们想要的函数形式：
Func<int, int> Fac = (x) => fac(fac, x);
综合以上过程，给出一个通用形式的帮助函数，简化类型推断：
static Func<T, TResult> Make<T, TR>(SelfApplicable<T, TR> self)
{
return (x) => self(self, x);
}
var fac = Make<int, int>((f, x) => (x <= 1) ? 1 : x * f(f, x - 1));
推广到两个参数的情形：
delegate TR SelfApplicable<T1, T2, TR>(SelfApplicable<T1, T2, TR> self, T1 arg1, T2 arg2);
static Func<T1, T2, TR> Make<T1, T2, TR>(SelfApplicable<T1, T2, TR> 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<int, int>((f) => (x) => (x <= 1) ? 1 : x * f(x - 1));
这需要配套怎样的 Make2 呢？
static Func<T, TR> Make2<T, TR>(Func<Func<T, TR>, Func<T, TR>> 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<T, TR> Fix<T, TR>(Func<Func<T, TR>, Func<T, TR>> g)
{
return (x) => g(Fix(g))(x);
}
Fix 要配合一种两层的匿名函数写法。其中递归函数自身作为外层函数的参数，Fix 将其转化为了可以直接使用的函数对象。
两个参数的 Fix 函数也可以顺利写出来了：
static Func<T1, T2, TR> Fix<T1, T2, TR>(Func<Func<T1, T2, TR>, Func<T1, T2, TR>> g)
{
return (x, y) => g(Fix(g))(x, y);
}
// 称为单步函数
var g0 = (f) => (x) => (x <= 1) ? 1 : x * f(x - 1);
var fac = Fix<int, int>(g0);
fac(5);
var g1 = (f) => (x, y) => (y == 0) ? x : f(y, x % y);
var gcd = Fix<int, int, int>(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) vf (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)
