替代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告诉我们,在多个地方有价值的代码不应该重复; 它应该被命名,因此可以从一个共同的地方访问.Lambdas本质上是一次性的; 一种指定几行特定情境的代码的方法,用于更通用的算法,如循环结构.大多数递归算法都具有相当普遍的应用(排序,递归系列生成等),这通常会使您可以更广泛地访问它们.

抛开Lambda演算,在大多数编程语言中,匿名函数F必须存在才能使用.这排除了函数本身的定义.在一些函数语言(如Erlang)中,函数F使用"重载"定义,其中较简单的函数用作更复杂函数的基本情况:

Fact(0) -> 1

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

这样就好了,除了在Erlang-world中这现在是一个命名函数"Fact",并且在调用该方法时,程序将"掉落"重载,直到找到参数匹配的第一个.在这个确切的构造中,C#中没有等价物,因为C#不支持根据值选择重载.

诀窍是以某种方式获得可以传递给函数的函数的引用.有许多方法,所有这些方法都需要预先存在的参考资料.如果您不能按名称引用该函数,则FP-combinator函数的类型为Func<Func<Func<Func<Func<....Konrad的方法是最简单的,但在C#中它最终会出现一种黑客攻击(它编译但是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<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次.设计用于功能性的更智能的语言将为您做到这一点.

Answer 2

Haskell Curry 发明了 Y 组合器来定义和使用无类型 lambda 演算中的匿名递归函数，定义如下：
\nY = \xce\xbbf\xc2\xb7(\xce\xbbx\xc2\xb7f (x x)) (\xce\xbbx\xc2\xb7f (x x))

\n\n

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

\n