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

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


当前回答

下面是Y-Combinator和Factorial函数的JavaScript实现(来自Douglas Crockford的文章,可在http://javascript.crockford.com/little.html上找到)。

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

其他回答

我认为回答这个问题的最好方法是选择一种语言,比如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组合子解决了什么问题。

JavaScript中的y组合子:

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

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

编辑: 通过查看代码,我学到了很多东西,但是如果没有一些背景知识,这个代码有点难以理解——对此我感到抱歉。有了其他答案提供的一些常识,你就可以开始分析正在发生的事情了。

The Y function is the "y-combinator". Now take a look at the var factorial line where Y is used. Notice you pass a function to it that has a parameter (in this example, recurse) that is also used later on in the inner function. The parameter name basically becomes the name of the inner function allowing it to perform a recursive call (since it uses recurse() in it's definition.) The y-combinator performs the magic of associating the otherwise anonymous inner function with the parameter name of the function passed to Y.

关于Y如何变魔术的完整解释,请查看链接文章(顺便说一下,不是我写的)。

对于那些没有深入接触过函数式编程,现在也不想开始,但有点好奇的程序员:

Y组合子是一个公式,它允许你在这样的情况下实现递归:函数不能有名称,但可以作为参数传递,用作返回值,并在其他函数中定义。

它的工作原理是将函数作为参数传递给自己,这样它就可以调用自己。

它是lambda演算的一部分,lambda演算实际上是数学,但实际上是一种编程语言,是计算机科学尤其是函数式编程的基础。

Y组合子的日常实用价值是有限的,因为编程语言倾向于让你命名函数。

如果你需要在警察的队列中识别它,它看起来是这样的:

Y = λf.(λx。F (x x)) (λx。F (x x))

你通常可以发现它,因为重复的(λx。F (x x))

λ符号是希腊字母,这是λ演算的名字,有很多(λx.t)风格的术语因为这就是λ演算的样子。

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

我想知道从头开始建立这个系统是否有任何用处。让我们来看看。这是一个基本的递归阶乘函数:

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

让我们重构并创建一个名为fact的新函数,它返回一个匿名的阶乘计算函数,而不是执行计算本身:

function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();

这有点奇怪,但这没什么问题。我们只是在每一步生成一个新的阶乘函数。

这个阶段的递归仍然相当明确。事实函数需要知道自己的名字。让我们参数化递归调用:

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

这很好,但是递归仍然需要知道自己的名字。让我们把它参数化:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

现在,我们不直接调用递归器(recurser),而是创建一个包装器函数,返回它的结果:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

现在我们可以完全去掉递归的名字;它只是Y内部函数的一个参数,可以用函数本身替换:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

唯一仍然引用的外部名称是fact,但现在应该清楚了,它也很容易参数化,创建完整的,通用的解决方案:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

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