从“函数”的角度来看,y组合子是一个计算机科学的概念。大多数程序员根本不了解组合子,如果他们听说过的话。
什么是y组合子? 组合符是如何工作的? 它们有什么用? 它们在过程语言中有用吗?
从“函数”的角度来看,y组合子是一个计算机科学的概念。大多数程序员根本不了解组合子,如果他们听说过的话。
什么是y组合子? 组合符是如何工作的? 它们有什么用? 它们在过程语言中有用吗?
当前回答
对于那些没有深入接触过函数式编程,现在也不想开始,但有点好奇的程序员:
Y组合子是一个公式,它允许你在这样的情况下实现递归:函数不能有名称,但可以作为参数传递,用作返回值,并在其他函数中定义。
它的工作原理是将函数作为参数传递给自己,这样它就可以调用自己。
它是lambda演算的一部分,lambda演算实际上是数学,但实际上是一种编程语言,是计算机科学尤其是函数式编程的基础。
Y组合子的日常实用价值是有限的,因为编程语言倾向于让你命名函数。
如果你需要在警察的队列中识别它,它看起来是这样的:
Y = λf.(λx。F (x x)) (λx。F (x x))
你通常可以发现它,因为重复的(λx。F (x x))
λ符号是希腊字母,这是λ演算的名字,有很多(λx.t)风格的术语因为这就是λ演算的样子。
其他回答
下面是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);
不动点组合子(或不动点运算符)是一种高阶函数,用于计算其他函数的一个不动点。此操作与编程语言理论相关,因为它允许以重写规则的形式实现递归,而不需要语言的运行时引擎的显式支持。(src维基百科)
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)。
如果你准备好长篇大论,Mike Vanier有一个很好的解释。长话短说,它允许您在一种不一定支持递归的语言中实现递归。
其他答案对此提供了相当简洁的答案,但没有一个重要的事实:你不需要用任何实用语言以这种令人费解的方式实现定点组合子,这样做没有任何实际目的(除了“看,我知道y组合子是什么”)。这是一个重要的理论概念,但没有什么实际价值。