替代的Y组合子定义

Question

我最近花了一些时间来理解Y组合子，我发现它通常被定义为以下内容（这是使用C#编写的，但所选语言并不重要）：

public delegate TResult SelfApplicable<TResult>(SelfApplicable<TResult> r);

public static TResult U<TResult>(SelfApplicable<TResult> r)
{
    return r(r);
}

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f)
{
    return U<Func<TArg1, TReturn>>(r => arg1 => f(U(r))(arg1));
}

虽然这是完全可行的（函数式），但似乎我的定义要简单得多：

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f)
{
    return f(n => Y(f)(n));
}

为什么后一种定义方式不如前者常见呢（我在网上还没有找到）？这可能与用自身来定义Y有关吗？

- Charles

---

天哪，Y组合子。我特意避免了我们课程中的那一部分，我的大脑正在溢出堆栈。但是加一，好问题无论如何。 - user541686

那是一个固定点组合器，但我不确定它是否真的是 Y 组合器。我也很好奇，让我们看看更有经验的人怎么说... - ephemient

Y组合子不是用来实现递归的吗？也就是说，你不能使用它来实现递归。 - Lou Franco

@Lou Franco：糟糕！是的，那听起来没错。如果语言支持高阶函数，Y将允许在本质上不支持递归的语言中实现递归。递归地定义Y会打败它最初的目的（尽管在某些情况下仍然有用）。 - Charles

你的定义看起来就像Haskell中fix函数的定义：fix f = let x = f x in x。[来源（haskell.org）]（http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Data-Function.html#fix） - Dan Burton

Answer 1

匿名递归，即使用固定点组合子的方式，在命令式、强类型语言中并不常见。原因很简单，因为给函数起一个名称比定义执行相同任务的匿名函数更容易。此外，面向对象分析与设计(OOA&D)教导我们，具有多个引用价值的代码不应重复，而应该命名，并从公共位置访问。Lambda表达式本质上是一次性的，它是指定几行非常特定代码以在更通用的算法（如循环结构）中使用的一种方式。大多数递归算法都是具有相当普遍应用的事物（如排序、递归序列生成等），这些算法通常会使它们变得更广泛可用。

除了λ演算之外，在大多数编程语言中，必须存在匿名函数F才能使用它。这排除了以自身为基础定义函数的可能性。在某些函数式语言（如Erlang）中，函数F是使用“重载”定义的，其中较简单的函数用作更复杂函数的基本情况：

Fact(0) -> 1

Fact(i) -> Fact(i-1) * i

这本来没问题，但在Erlang世界中这是一个命名函数“Fact”，调用该方法时程序会“落”到一个重载上，直到找到第一个参数匹配的重载为止。在C#中没有这样精确的构造，因为C#不支持基于值选择重载。

关键是要以某种方式获得可以传递给函数的函数引用。有许多方法，所有方法都需要预先存在的引用。如果无法通过名称引用函数，则FP组合器函数的类型为Func<Func<Func<Func<Func<...。Konrad的方法最简单，但在C#中却成了一种hack（虽然它编译了，但ReSharper仍然会抱怨它可能会引发InvalidOperationException；无法调用空方法指针）。

以下是我在简单情况下使用的代码，基本上使用委托解决了不能隐式类型化隐式类型化lambda的问题：

public static class YCombinator
{
    public delegate TOut RLambda<TIn, TOut>(RLambda<TIn, TOut> rLambda, TIn a);
    public static Func<T,T> Curry<T>(this RLambda<T,T> rLambda)
    {
        return a => rLambda(rLambda, a);
    }
}

//usage
var curriedLambda = YCombinator.Curry<int>((f, i) => i <= 0 ? 1 : f(f, i - 1)*i)
var shouldBe120 = curriedLambda(5);

您可以声明一个Curry<TIn, TOut>重载函数来处理输入类型与输出类型不同的情况，例如生成前N个质数列表等；该函数P可以被递归地定义为产生所有不被任何较小的质数整数整除的正整数列表函数。固定点P(1) => 2定义了一个基本情况，递归算法可以从中定义（尽管不是很高效）：

var curriedLambda =
            YCombinator.Curry<int, List<int>>(
                (p, i) => i == 1
                              ? new List<int>{2}
                              : p(p, i - 1)
                                    .Concat(new[]
                                                {
                                                    Enumerable.Range(p(p, i - 1)[i - 2],
                                                                     int.MaxValue - p(p, i - 1)[i - 2])
                                                        .First(x => p(p, i - 1).All(y => x%y != 0))
                                                }).ToList()
                );
        Assert.AreEqual(new []{2,3,5,7,11}, curriedLambda(5));

因此，难题出现了;虽然你当然可以将所有内容定义为高阶函数，但是如果以命令式而不是函数式的方式定义这个素数查找器，它会更快。主要的加速是在每个级别上定义p(p，i-1)，使其不被每个递归级别评估3次。一种更智能的设计用于函数工作的语言会为您做到这一点。

- KeithS

Answer 2

我不确定您的问题是什么，但我猜想既然Y组合器也不常见于您的解决方案中，那么原因有两个：与HTML标签保持一致，请勿添加任何解释。

1. anonymous recursive functions are really rare; in particular since C# doesn’t have great (read: none at all) support for tail recursion.

2. There’s a much easier (more readable for the uninitiated) way of defining pseudo-“anonymous” recursive lambdas in C#:

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

   Granted, this is not anonymous but it’s “close enough” for practical purposes.

- Konrad Rudolph

---

即使在Scheme中定义的Y组合器也不是“匿名的”; 为了在您的方法中引用它，您必须调用SOMETHING函数，并且Scheme解释与此处发生的情况非常接近（定义fac存在，然后创建使用fac的lambda并将其分配给fac）。 - KeithS

@Keith：“你必须调用函数SOMETHING才能引用它” - 实际上不需要：Y(f => x => x == 0 ? 1 : x * f(x - 1))(5) == 120。这与我的示例根本不同，因为它仍然适用于不可变变量，即当您无法重新定义fac的含义时，就像我在代码中所做的那样。 - Konrad Rudolph

当然，这是通过将“匿名”函数绑定到封闭lambda的参数符号（f）来“欺骗”的。 - Konrad Rudolph

这个定义虽然简单，但在复制时存在问题，如此处所述： http://blogs.msdn.com/b/wesdyer/archive/2007/02/02/anonymous-recursion-in-c.aspx - Tony

Answer 3

Haskell Curry发明了Y组合子，用于在未类型化的λ演算中定义和使用匿名递归函数，其定义如下：
Y = λf·(λx·f (x x)) (λx·f (x x)) 我的定义打败了Y组合子的原始目的，因为它依赖于C＃固有的支持来定义递归函数。然而，它仍然很有用，因为它允许在C＃中定义匿名递归函数。

- Charles