备选方案Y组合子定义 [英] Alternative Y combinator definition

问题描述

我花了一些时间我的包裹绕Y组合子头部最近，我发现，它通常被定义（或多或少）如下（这是在C＃中，但所选择的语言并不重要）：

I've spent some time wrapping my head around the Y combinator lately, and I've found that it is usually defined (more or less) as follows (this is in C#, but the language of choice isn't important):

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

虽然这是完美的功能（双关语意） ，它似乎是我的定义简单得多：

While that's perfectly functional (pun intended), it would seem that my definition is much simpler:

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

是否有任何理由，后者定义并不像常见的（我还没有找到它的净）？它或许会有些事情要与本身来定义Y'

Is there any reason why the latter definition is not as common (I have yet to find it on the net)? Would it perhaps have something to do with defining Y in terms of itself?

推荐答案

匿名递归，即一个不动点组合子，是不是经常看到势在必行，强类型语言，对于原因很简单，很容易命名[删]功能比来定义执行相同的任务匿名函数。此外，OOA和D教导我们有在多个地方的价值不应该被重复的代码;它应该被命名，因此从一个共同的地方访问。 Lambda表达式是由他们的自然一次性的;指定像循环结构更一般的算法的使用非常具体的情况，几行代码的方法。大多数递归算法的东西，有相当普遍的应用（分类，递推数列的产生，等等），这通常会导致你使他们更广泛地使用。

Anonymous recursion, i.e. with a fixed point combinator, is not often seen in imperative, strongly-typed languages, for the very simple reason that it is easier to name your [censored] function than to define an anonymous function that performs the same task. Also, OOA&D teaches us that code which has value in multiple places shouldn't be duplicated; it should be named and thus accessible from a common place. Lambdas are by their very nature a one-off; a way of specifying a few lines of very situation-specific code for use in a more general algorithm like looping constructs. Most recursive algorithms are things that have pretty general application (sorting, recursive series generation, etc), which generally lead to you making them more widely accessible.

LAMBDA演算不谈，大多数编程语言必须存在一个匿名函数F可以使用它。排除对自身而言函数的定义。

Lambda calculus aside, in most programming languages an anonymous function F must exist before it can be used. That precludes the definition of a function in terms of itself. In some functional languages such as Erlang, the function F is defined using "overloads", where simpler functions are used as base cases for more complex ones:

Fact(0) -> 1

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

这将是罚款，但在二郎山世界，这是现在名为函数事实，并调用该方法程序将落，通过重载，直到它找到的第一个为其参数（S）的比赛时。没有在C＃中相当于这个确切的构造，因为C＃不支持选择基于价值的过载。

This would be fine, except that in Erlang-world this is now a named function "Fact", and when calling that method the program will "fall" through the overloads until it finds the first one for which the parameter(s) match. There isn't an equivalent in C# to this exact construct because C# doesn't support choosing an overload based on value.

诀窍就是以某种方式得到的一个参考功能可传递给函数。有很多方法，所有这些都需要一个预先存在的参考某处。如果不能按名称引用的函数，那么FP-组合器功能的类型是 Func键< Func键< Func键< Func键< Func键< ... 。康拉德的方法是最简单的，但在C＃它结束了怎样的一个黑客（它编译但仍ReSharper的抱怨，这是一个可能出现InvalidOperationException;不能调用空方法指针）。

The trick is to somehow get a reference to the function that can be passed to the function. There are many ways, all of which require a pre-existing reference SOMEWHERE. If you can't refer to the function by name, then the type of the FP-combinator function is Func<Func<Func<Func<Func<.... Konrad's method is the easiest, but in C# it ends up kind of a hack (it compiles but ReSharper still complains that it's a possible InvalidOperationException; can't invoke a null method pointer).

这里的东西我用简单的情况下，基本上都采用委托解决方法不能够隐式类型的隐式类型lambda：

Here's something I use for simple cases, basically using the delegate workaround for not being able to implicitly type an implicitly-typed 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);

您可以声明咖喱<锡，兜售> 过载来处理的情况下的输入类型不是输出型，如产前N素数的列表;该函数P可以递归定义为产生不属于任何较少素数整除所有正整数的列表的功能。固定点P（1）=> 2定义了从其中递归算法可以定义一个基本情况（尽管不是很有效的）：

You can declare a Curry<TIn, TOut> overload to handle cases where the input type isn't the output type, such as producing a list of the first N prime numbers; that function P can be recursively defined as the function which produces a list of all positive integers which are not divisible by any lesser prime number. The fixed point P(1) => 2 defines a base case from which a recursive algorithm can be defined (albeit not a very efficient one):

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倍。设计功能工作的一个聪明的语言会为你做的。

And thus the conundrum presents itself; though you certainly CAN define everything as a higher-order function, this prime-finder would be MUCH faster if defined imperatively instead of functionally. The main speedup is simply defining p(p,i-1) at each level so it isn't evaluated 3 times per recursion level. A smarter language designed to work functionally would do that for you.

这篇关于备选方案Y组合子定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！