从“函数”的角度来看,y组合子是一个计算机科学的概念。大多数程序员根本不了解组合子,如果他们听说过的话。
什么是y组合子? 组合符是如何工作的? 它们有什么用? 它们在过程语言中有用吗?
从“函数”的角度来看,y组合子是一个计算机科学的概念。大多数程序员根本不了解组合子,如果他们听说过的话。
什么是y组合子? 组合符是如何工作的? 它们有什么用? 它们在过程语言中有用吗?
当前回答
上面的大多数答案描述了y组合子是什么,但没有描述它的用途。
用不动点组合子来证明lambda演算是图灵完备的。这是计算理论中一个非常重要的结果,为函数式编程提供了理论基础。
学习不动点组合子也帮助我真正理解了函数式编程。但我从未发现它们在实际编程中有任何用处。
其他回答
下面是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组合子是一个公式,它允许你在这样的情况下实现递归:函数不能有名称,但可以作为参数传递,用作返回值,并在其他函数中定义。
它的工作原理是将函数作为参数传递给自己,这样它就可以调用自己。
它是lambda演算的一部分,lambda演算实际上是数学,但实际上是一种编程语言,是计算机科学尤其是函数式编程的基础。
Y组合子的日常实用价值是有限的,因为编程语言倾向于让你命名函数。
如果你需要在警察的队列中识别它,它看起来是这样的:
Y = λf.(λx。F (x x)) (λx。F (x x))
你通常可以发现它,因为重复的(λx。F (x x))
λ符号是希腊字母,这是λ演算的名字,有很多(λx.t)风格的术语因为这就是λ演算的样子。
我想知道从头开始建立这个系统是否有任何用处。让我们来看看。这是一个基本的递归阶乘函数:
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);
};
});
我从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行替换为 任何你想要的递归函数。
如果你准备好长篇大论,Mike Vanier有一个很好的解释。长话短说,它允许您在一种不一定支持递归的语言中实现递归。