14

我的大脑似乎处于自虐模式，所以在淹没在这个、这个和这个中之后，它想在 C# 中搞一些 DIY。

我想出了以下内容，我认为它不是Y 组合器，但它似乎确实设法使非递归函数递归，而不涉及自身：

Func<Func<dynamic, dynamic>, Func<dynamic, dynamic>> Y = x => x(x);

因此，鉴于这些：

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(self)(n - 1);
Func<dynamic, Func<dynamic, dynamic>> fib = 
                  self => n => n < 2 ? n : self(self)(n-1) + self(self)(n-2);

我们可以生成这些：

Func<dynamic, dynamic> Fact = Y(fact);
Func<dynamic, dynamic> Fib = Y(fib);

Enumerable.Range(0, 10)
          .ToList()
          .ForEach(i => Console.WriteLine("Fact({0})={1}", i, Fact(i)));

Enumerable.Range(0, 10)
          .ToList()
          .ForEach(i => Console.WriteLine("Fib({0})={1}", i, Fib(i)));
4

1 回答 1

7

不，那不是 Y 组合器；你只完成了一半。您仍然需要在应用它的“种子”功能中排除自我应用。也就是说，而不是这样：

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(self)(n - 1);

你应该有这个：

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(n - 1);

注意第二个定义中的单个出现，self而不是第一个定义中的两个出现。

（编辑添加：）顺便说一句，由于您使用 C# 模拟具有按值调用评估的 lambda 演算，因此您想要的定点组合器通常称为 Z，而不是 Y

（再次编辑以详细说明：）描述的等式Y是这样的（有关推导，请参见维基百科页面）：

Y g = g (Y g)

但是在大多数实用的编程语言中，您在调用函数之前评估函数的参数。在编程语言社区中，这称为按值调用评估（不要与 C/C++/Fortran/etc 程序员区分“按值调用”与“按引用调用”与“按复制恢复调用”的方式相混淆， ETC）。

但如果我们这样做，我们会得到

Y g = g (Y g) = g (g (Y g)) = g (g (g (Y g))) = ...

也就是说，我们将所有时间都花在构建递归函数上，而永远不会去应用它。

另一方面，在按名称调用评估中，您将函数 here 应用于未评估g的参数表达式 here (Y g)。但是 if gis like fact，它在做任何事情之前都在等待另一个参数。g因此，在尝试进一步评估之前，我们将等待第二个参数(Y g)--- 并且取决于函数的作用（即，如果它具有基本情况），我们可能根本不需要评估(Y g)。这就是Y名称调用评估有效的原因。

按值调用的解决方法是改变等式。而不是Y g = g (Y g)，我们想要类似以下等式的东西：

Z g = g (λx. (Z g) x)

（我想我的方程是正确的，或者接近正确的。你可以计算出来，看看它是否符合 的定义Z。）

考虑这一点的一种方法是，不是计算“整个递归函数”并将其交给g，而是交给它一个函数，该函数将一次计算一点递归函数——而且只有在我们实际上需要更多的时候因此我们可以将其应用于参数 ( x)。

于 2011-10-06T06:11:58.877 回答