替代 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));
}

< br> 虽然这是完美的功能（双关语），但我的定义似乎要简单得多：

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

后一个定义不那么常见有什么原因吗（我还没有在网上找到它）？这可能与 Y 本身的定义有关吗？

Answer 1

我不确定你的问题是什么，但我猜 Y 组合器和你的解决方案在野外都很少见到的原因是双重的：

1. 匿名递归函数确实很少见；特别是因为 C# 对尾递归没有很好的支持（读作：根本没有）。

2. 在 C# 中定义伪“匿名”递归 lambda 有一种更简单（对于外行来说更易读）的方法：

   Func;事实=空；
   fac = x => x == 0 ? 1：fac(x - 1) * x；
   

   当然，这不是匿名，但对于实际目的来说它“足够接近”。

Answer 2

Haskell Curry 发明了 Y 组合器来定义和使用无类型 lambda 演算中的匿名递归函数，定义如下：
Y = λf·(λx·f (xx)) (λx·f (xx))

我的定义违背了 Y 的初衷组合器，因为它依赖于 C# 对定义递归函数的固有支持。然而，它仍然很有用，因为它允许在 C# 中定义匿名递归函数。

Answer 3

匿名递归，即带有定点组合器，在命令式强类型语言中并不常见，原因很简单，命名你的[审查]函数比定义执行相同任务的匿名函数更容易。此外，OOA&D 告诉我们，在多个地方有价值的代码不应该重复；它应该被命名，从而可以从一个公共地方访问。 Lambda 本质上是一次性的。一种指定几行非常特定于情况的代码的方法，用于更通用的算法（如循环结构）。大多数递归算法都有相当普遍的应用（排序、递归序列生成等），这通常会导致您使它们更广泛地可用。

除了 Lambda 演算之外，在大多数编程语言中，匿名函数 F 必须存在才能使用。这就排除了函数本身的定义。在一些函数式语言（例如 Erlang）中，函数 F 是使用“重载”来定义的，其中更简单的函数被用作更复杂函数的基本情况：

Fact(0) -> 1

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

这很好，除了在 Erlang 世界中，它现在是一个命名函数“Fact” ”，并且当调用该方法时，程序将“失败”通过重载，直到找到参数匹配的第一个。 C# 中没有与此精确构造等效的结构，因为 C# 不支持根据值选择重载。

诀窍在于以某种方式获得对可以传递给函数的函数的引用。有很多方法，所有这些都需要预先存在的参考。如果无法通过名称引用函数，则 FP 组合器函数的类型为 Func。 Konrad 的方法是最简单的，但在 C# 中它最终会导致某种 hack（它可以编译，但 ReSharper 仍然抱怨它可能是 InvalidOperationException；无法调用 null 方法指针）。

以下是我用于简单情况的方法，基本上使用委托解决方法来解决无法隐式键入隐式类型 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 重载来处理输入的情况type 不是输出类型，例如生成前 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 次评估。一种设计为功能性工作的更智能的语言可以为您做到这一点。