《Fish and Scales》      作者：埃舍尔

本系列文章目录：

 

我们实现 Y 组合子，这篇文章讨论 Θ 组合子的实现。（Θ 读 Theta，希腊语第八个字母，小写为 θ。）

继续使用前文中的类型假定，假定递归函数：

• 参数为 int；
• 返回值为 long。

Θ 组合子

Θ 组合子也是一个常见不动点组合子，由 发现，也称为图灵不动点组合子:

1	Θ = (λx.λy.(y(x x y))) (λx.λy.(y(x x y)))

传值调用形式为（(x x y) η-展开为 λz. x x y z）：

1	Θv = (λx.λy.(y(λz. x x y z))) (λx.λy.(y(λz. x x y z)))

不过我还是喜欢把 y (x x y) η-展开为： λn.(y (x x y) n)，得出：

1	Θ = (λx.λy.λn.(y(x x y) n)) (λx.λy.λn.(y(x x y) n))

定义一个中间变量 h，令：

1	h = λx.λy.λn.(y(x x y)n)

则：

1	Θ = h h Θ = h(h)

实现 h

确定 h 的类型

根据的推断，Θ 的类型为 Func<Func<Func<int, long>, Func<int, long>>, Func<int, long>> , 这也是 h 返回值的类型。

h 可调用自身 h(h)，需要用到 用的 SelfApplicable<TResult>委托：

1	delgate TResult ( self);

h 的类型为：SelfApplicable<Func<Func<Func<int, long>, Func<int, long>>, Func<int, long>>>。

实现 h

对 h 作一步简单变换：

1 2	h = λx.λy.λn.(y(x x y)n) h = λx.λy.λn.(y(x(x)(y))(n)

使用总结出的规律，可写出：

1	<<<<, >, <, >>, <, >>> h = x => y => n => y(x(x)(y))(n);

实现 Θ

根据 Θ 的简单式：

1

Θ = h(h)

可写出：

1	<<<, >, <, >>, <, >> Θ = h(h);

与 h 的代码放在一块：

1 2	<<<<, >, <, >>, <, >>> h = x => y => n => y(x(x)(y))(n); <<<, >, <, >>, <, >> Θ = h(h);

还记得 最后给出的代吗？（出处：）

比较下，看看是不是一回事的。

调用下试试：

12	var factorial = Θ(f => x => x == 0 ? 1 : x * f(x - 1));var result = factorial(5); // 120

封装 Θ

12345678910

public class { public static Fix (< , > f) { return .Fix(f); } static class { delegate T ( self); static readonly <<< , >, >> h = x => y => n => y(x(x)(y))(n); public static readonly << , >, > Fix = h(h); }}

调用示例代码：

12345

var factorial = ThetaCombinator.Fix (f => n => n == 0 ? 1 : n * f(n - 1));var result1 = factorial(5); // 120var fibonacci = ThetaCombinator.Fix (f => n => n < 2 ? n : f(n - 1) + f(n - 2));var result2 = fibonacci(5); // 5

后记

文中也给出了下面一种简单到极致的写法：

123	Fix (< , > F) { return t => F(Fix(F))(t);}

增加一个泛型参数并修改下参数的名称，得出：

1	Fix (< , > f) { return t => f(Fix(f))(t);}

便是 给出的写法。 中将说明这个是如何编导出的。