我是否已经使用C#动态实现了Y组合子？如果没有，什么是它？

Question

我是否已经使用C#动态实现了Y组合子？如果没有，什么是它？

c#dynamicfunctional-programmingy-combinator

14

我似乎沉迷于自虐模式，所以在阅读完这篇文章、这篇文章和这篇文章后，它想要用C#尝试一些自己动手的东西。

我想出了以下代码，我不认为这是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)));

- Benjol

这是U组合子：U x = x x，以组合子符号表示。 - Will Ness

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ryan Culpepper · Accepted Answer

不，那不是 Y combinator；你只完成了一半。你还需要在“种子”函数中分解自我应用。也就是说，不要这样写：

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演算，并采用值调用的评估方式，因此您需要的不是Y组合子，而是经常被称为Z的组合子（请参见其他固定点组合子）。

（再次编辑以阐明：）描述Y的方程式如下（请参见维基百科页面以获取推导）：

Y g = g (Y g)

但是在大多数实用编程语言中，你在调用函数之前会先计算出函数的参数。在编程语言社区中，这被称为按值调用（不要与C/C++/Fortran等程序员区分“按值调用”和“按引用调用”以及“按复制-恢复调用”等方式混淆）。

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

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

也就是说，我们会花费所有时间构建递归函数，并且永远无法应用它。而在按名调用计算中，您将一个函数（此处为g）应用于未求值的参数表达式（此处为(Y g)）。但是，如果g类似于fact，那么它在执行任何操作之前都在等待另一个参数。因此，在尝试进一步评估(Y g)之前，我们需要等待第二个参数传入g。根据函数的实际情况（即它是否具有基本情况），我们甚至可能根本不需要评估(Y g)。这就是为什么Y可用于按名调用计算的原因。

对于按值调用，则需要更改方程。我们需要像下面这个方程一样，而不是Yg=g(Yg)。

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

(我认为我已经得到了正确的方程式，或者接近正确。您可以计算一下，看它是否符合Z的定义。)

一种思考方式是，我们不去计算“整个递归函数”并将其交给g，而是将一个函数交给它，这个函数会一次计算一点递归函数——当我们需要更多的函数来将其应用于参数(x)时才计算。