从“函数”的角度来看,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-Combinator,我在Clojure和Scheme中都写了一份关于Y-Combinator的“傻瓜指南”。他们受到了《小阴谋家》的影响
在方案: https://gist.github.com/z5h/238891
Clojure: https://gist.github.com/z5h/5102747
这两个教程都是代码中穿插的注释,应该剪切和粘贴到您最喜欢的编辑器。
Y-Combinator是通量电容器的另一个名称。
我从http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html中引用了这个,这是我几年前写的一个解释。
在本例中我将使用JavaScript,但许多其他语言也可以。
我们的目标是写出一个1的递归函数 变量只使用1变量的函数,没有 赋值,通过名称定义事物等(为什么这是我们的 目标是另一个问题,我们把它作为 我们所面临的挑战。)似乎不可能,是吧?作为 举个例子,让我们实现阶乘。
第一步是说我们可以很容易地做到这一点,如果我们 作弊了一点。使用二元函数和 我们至少可以避免使用 赋值来建立递归。
// Here's the function that we want to recurse.
X = function (recurse, n) {
if (0 == n)
return 1;
else
return n * recurse(recurse, n - 1);
};
// This will get X to recurse.
Y = function (builder, n) {
return builder(builder, n);
};
// Here it is in action.
Y(
X,
5
);
现在我们看看能不能少作弊。首先我们用 任务,但我们不需要。我们可以写成X和 Y内联。
// No assignment this time.
function (builder, n) {
return builder(builder, n);
}(
function (recurse, n) {
if (0 == n)
return 1;
else
return n * recurse(recurse, n - 1);
},
5
);
但是我们用两个变量的函数来得到一个1的函数 变量。我们能解决这个问题吗?一个叫 Haskell Curry有一个巧妙的技巧,如果你有好的高阶 那么你只需要一个变量的函数。的 证明是你可以从函数2(或更多) 一般情况下)变量以1变量为纯粹 像这样的机械文本转换:
// Original
F = function (i, j) {
...
};
F(i,j);
// Transformed
F = function (i) { return function (j) {
...
}};
F(i)(j);
在那里……完全一样。(这个技巧叫做 “模仿”它的发明者。Haskell也是一种语言 以哈斯克尔·库里命名。把它归为无用的琐事。) 现在只要把这个变换应用到任何地方,我们就得到 我们的最终版本。
// The dreaded Y-combinator in action!
function (builder) { return function (n) {
return builder(builder)(n);
}}(
function (recurse) { return function (n) {
if (0 == n)
return 1;
else
return n * recurse(recurse)(n - 1);
}})(
5
);
尽管试一试。Alert()返回,将其绑定到一个按钮,等等。 该代码不使用,递归地计算阶乘 2变量的赋值、声明或函数。(但 试图追踪它是如何工作的可能会让你头晕目眩。 递过来,没有推导,只是稍微重新格式化了一下 会导致代码令人困惑。)
可以将递归定义阶乘的4行替换为 任何你想要的递归函数。
其他答案对此提供了相当简洁的答案,但没有一个重要的事实:你不需要用任何实用语言以这种令人费解的方式实现定点组合子,这样做没有任何实际目的(除了“看,我知道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将发散/无限循环)。