# 探索匿名递归函数

09/06 03:36

## 匿名递归

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

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

## 将自己传给自己

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

``````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);
``````

``````Func<int, int> Fac = (x) => fac(fac, x);
``````

``````static Func<T, TR> 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));
``````

``````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;
}
``````

``````static Func<T, TR> Fix<T, TR>(Func<Func<T, TR>, Func<T, TR>> g)
{
return (x) => g(Fix(g))(x);
}
``````

`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);
}
``````
``````// g0 也可称为单步函数
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));
``````

``````// 注意：这是方便理解而拆开的伪代码，因为不可能使 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);
``````

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

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

## Y-组合子

Y-组合子定义为：

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

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

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

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

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

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

0
5 收藏

### 作者的其它热门文章

public static readonly Action<object> ShowMessage = EventAggregator<object>.CreateEvent(() => ShowMessage);
09/19 20:51

09/11 21:54

09/11 10:24

3 评论
5 收藏
0