从“函数”的角度来看,y组合子是一个计算机科学的概念。大多数程序员根本不了解组合子,如果他们听说过的话。
什么是y组合子? 组合符是如何工作的? 它们有什么用? 它们在过程语言中有用吗?
从“函数”的角度来看,y组合子是一个计算机科学的概念。大多数程序员根本不了解组合子,如果他们听说过的话。
什么是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组合子实现匿名递归。所以与其
function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }
你可以这样做
function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }
当然,y-combinator只适用于按名字命名的语言。如果你想在任何正常的值调用语言中使用它,那么你将需要相关的z-combinator (y-combinator将发散/无限循环)。
如果你准备好长篇大论,Mike Vanier有一个很好的解释。长话短说,它允许您在一种不一定支持递归的语言中实现递归。
下面是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);
其他答案对此提供了相当简洁的答案,但没有一个重要的事实:你不需要用任何实用语言以这种令人费解的方式实现定点组合子,这样做没有任何实际目的(除了“看,我知道y组合子是什么”)。这是一个重要的理论概念,但没有什么实际价值。
我认为回答这个问题的最好方法是选择一种语言,比如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组合子解决了什么问题。