Y-结合子
视频锁定
{$ currentTime | date:'mm:ss' $}
{$ timeLeft | date:'mm:ss' $}
提到递归,函数式语言中还有一个很有意思的主题,即:如果一个函数是匿名函数,能不能进行递归操作呢?如何可以,怎么做?我们还是来看阶乘的例子:
function factorial(x){
return x == 0 ? 1 : x * factorial(x-1);
}
factorial 函数中,如果 x 值为 0,则返回 1,否则递归调用 factorial,参数为 x 减 1,最 后当 x 等于 0 时进行规约,最终得到函数值(事实上,命令式程序语言中的递归的概念最早 即来源于函数式编程中)。现在考虑:将 factorial 定义为一个匿名函数,那么在函数内部,在代码 x*factorial(x-1)的地方,这个 factorial 用什么来替代呢?
lambda 演算的先驱们,天才的发明了一个神奇的函数,成为 Y-结合子。使用 Y-结合子,可以做到对匿名函数使用递归。关于 Y-结合子的发现及推导过程的讨论已经超出了本部分的范围,有兴趣的读者可以参考附录中的资料。我们来看看这个神奇的 Y-结合子:
var Y = function(f) { return (function(g) {
return g(g); })(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
}; });
};
我们来看看如何运用 Y-结合子,依旧是阶乘这个例子:
var factorial = Y(function(func){
return function(x){
return x == 0 ? 1 : x * func(x-1);
}
});
factorial(10);
或者:
Y(function(func){
return function(x){
return x == 0 ? 1 : x * func(x-1);
}
})(10);
不要被上边提到的 Y-结合子的表达式吓到,事实上,在 JavaScript 中,我们有一种简单的方法来实现 Y-结合子:
var fact = function(x){
return x == 0 : 1 : x * arguments.callee(x-1);
}
fact(10);
或者:
(function(x){
return x == 0 ? 1 : x * arguments.callee(x-1);
})(10);//3628800
其中,arguments.callee 表示函数自身,而 arguments.caller
表示函数调用者,因此省去了很多复杂的步骤。
在线练习
{$ activeFileHint $}