从“函数”的角度来看,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组合子是什么,但没有描述它的用途。
用不动点组合子来证明lambda演算是图灵完备的。这是计算理论中一个非常重要的结果,为函数式编程提供了理论基础。
学习不动点组合子也帮助我真正理解了函数式编程。但我从未发现它们在实际编程中有任何用处。
为了帮助自己掌握Y-Combinator,我在Clojure和Scheme中都写了一份关于Y-Combinator的“傻瓜指南”。他们受到了《小阴谋家》的影响
在方案: https://gist.github.com/z5h/238891
Clojure: https://gist.github.com/z5h/5102747
这两个教程都是代码中穿插的注释,应该剪切和粘贴到您最喜欢的编辑器。
我想知道从头开始建立这个系统是否有任何用处。让我们来看看。这是一个基本的递归阶乘函数:
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);
};
});
下面是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组合子是什么”)。这是一个重要的理论概念,但没有什么实际价值。