c# - 替代 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 有关系吗？

Answer 1

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

撇开 Lambda 演算不谈，在大多数编程语言中，匿名函数 F 必须存在才能使用。这排除了根据自身定义函数。在某些函数式语言(例如 Erlang)中，函数 F 是使用“重载”定义的，其中更简单的函数用作更复杂函数的基本情况:

Fact(0) -> 1

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

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

诀窍在于以某种方式获得对可以传递给函数的函数的引用。有很多方法，所有这些方法都需要一个预先存在的引用 SOMEWHERE。如果不能通过名称引用函数，那么 FP-combinator 函数的类型是 Func<Func<Func<Func<Func<... . Konrad 的方法是最简单的，但在 C# 中它最终有点像 hack(它编译但 ReSharper 仍然提示它可能是 InvalidOperationException；不能调用空方法指针)。

这是我在简单情况下使用的东西，基本上是使用委托(delegate)解决方法来解决无法隐式键入隐式类型的 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 次。设计用于功能性工作的更智能的语言可以为您做到这一点。