从“函数”的角度来看,y组合子是一个计算机科学的概念。大多数程序员根本不了解组合子,如果他们听说过的话。

什么是y组合子? 组合符是如何工作的? 它们有什么用? 它们在过程语言中有用吗?


当前回答

this运算符可以简化你的生活:

var Y = function(f) {
    return (function(g) {
        return g(g);
    })(function(h) {
        return function() {
            return f.apply(h(h), arguments);
        };
    });
};

这样就避免了额外的函数:

var fac = Y(function(n) {
    return n == 0 ? 1 : n * this(n - 1);
});

最后,调用fac(5)。

其他回答

Y-combinator是一个“函数”(一个作用于其他函数的函数),当你不能从内部引用函数时,它可以实现递归。在计算机科学理论中,它概括了递归,抽象了递归的实现,从而将递归与函数的实际工作分离开来。递归函数不需要编译时名称的好处是一种额外的好处。=)

这适用于支持lambda函数的语言。lambdas基于表达式的特性通常意味着它们不能通过名称引用自己。通过声明变量,引用它,然后赋值给它,来完成自引用循环,是很脆弱的。可以复制lambda变量,并重新分配原始变量,这将破坏自引用。

y组合子在静态类型语言(过程性语言通常如此)中实现起来很麻烦,而且经常使用起来也很麻烦,因为通常类型限制要求在编译时知道函数的参数数量。这意味着必须为需要使用的任何参数count编写y-combinator。

下面是一个在c#中如何使用和工作的Y-Combinator的例子。

使用y组合子涉及到一种构造递归函数的“不寻常”方式。首先,你必须把你的函数写成一段代码,调用一个已经存在的函数,而不是它自己:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

然后将其转换为一个函数,该函数接受一个要调用的函数,并返回一个这样做的函数。这被称为函数,因为它接受一个函数,并对其执行一个操作,该操作产生另一个函数。

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

现在你有了一个函数,它接受一个函数,并返回另一个函数,它看起来像一个阶乘,但它不是调用它自己,而是调用传递给外部函数的参数。怎么把它变成阶乘呢?将内部函数传递给自身。Y-Combinator就是这样做的,它是一个具有永久名称的函数,可以引入递归。

// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
  return
    t =>  // A function that...
      F(  // Calls the factorial creator, passing in...
        Y(F)  // The result of this same Y-combinator function call...
              // (Here is where the recursion is introduced.)
        )
      (t); // And passes the argument into the work function.
}

不是阶乘调用自身,而是阶乘调用阶乘生成器(由对Y-Combinator的递归调用返回)。根据t的当前值,从生成器返回的函数会再次调用生成器,用t - 1,或者直接返回1,终止递归。

它是复杂而神秘的,但在运行时,它的工作关键是“延迟执行”,并将递归分解为跨越两个函数。内部的F作为参数传递,仅在必要时才在下一次迭代中调用。

我认为回答这个问题的最好方法是选择一种语言,比如JavaScript:

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}

现在重写它,使它不使用函数内部的函数名,但仍然递归地调用它。

函数名factorial唯一应该看到的地方是在调用位置。

提示:不能使用函数名,但可以使用参数名。

解决这个问题。不要去查。一旦你解决了它,你就会明白y组合子解决了什么问题。

不动点组合子(或不动点运算符)是一种高阶函数,用于计算其他函数的一个不动点。此操作与编程语言理论相关,因为它允许以重写规则的形式实现递归,而不需要语言的运行时引擎的显式支持。(src维基百科)

上面的大多数答案描述了y组合子是什么,但没有描述它的用途。

用不动点组合子来证明lambda演算是图灵完备的。这是计算理论中一个非常重要的结果,为函数式编程提供了理论基础。

学习不动点组合子也帮助我真正理解了函数式编程。但我从未发现它们在实际编程中有任何用处。

如果你准备好长篇大论,Mike Vanier有一个很好的解释。长话短说,它允许您在一种不一定支持递归的语言中实现递归。