从“函数”的角度来看,y组合子是一个计算机科学的概念。大多数程序员根本不了解组合子,如果他们听说过的话。
什么是y组合子? 组合符是如何工作的? 它们有什么用? 它们在过程语言中有用吗?
从“函数”的角度来看,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将发散/无限循环)。
其他回答
以下是对尼古拉斯·曼库索(Nicholas Mancuso)在回答中提到的文章(完全值得一读)中提到的原始问题的回答,以及其他答案:
什么是y组合子?
y组合子是一个“函数”(或高阶函数——一个作用于其他函数的函数),它接受一个参数,这是一个非递归的函数,并返回该函数的一个递归版本。
有点递归=),但更深入的定义:
一个组合子-就是一个没有自由变量的lambda表达式。 自由变量-是一个变量,不是一个约束变量。 绑定变量—包含在lambda表达式体中的变量,该变量名作为其参数之一。
另一种思考方式是,combinator是这样一个lambda表达式,在其中,你可以在任何地方用它的定义替换一个组合子的名称,并且一切都仍然有效(如果combinator在lambda体中包含对自身的引用,你将进入一个无限循环)。
y组合子是一个定点组合子。
函数的不动点是函数定义域中映射到函数自身的一个元素。 也就是说,如果f(c) = c, c是函数f(x)的一个不动点 这意味着f(f(…f(c)…))= fn(c) = c
组合符是如何工作的?
下面的例子假设强+动态类型:
惰性(正规阶)y组合子: 此定义适用于具有lazy(也称为deferred, call-by-need)求值的语言——该求值策略将表达式的求值延迟到需要它的值时。
Y = λf.(λx.f(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))
这意味着,对于给定的函数f(它是非递归函数),可以通过计算λx得到对应的递归函数。F (x x)然后把这个表达式应用到自身上。
严格(应用阶)y组合子: 这个定义适用于具有严格求值策略(也包括热切求值和贪婪求值策略)的语言,在这种策略中,表达式一旦绑定到变量就会被求值。
Y = λf.(λx.f(λy.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))
它本质上和lazy一样,只是有一个额外的λ包装器来延迟lambda的体计算。我问了另一个问题,和这个话题有点相关。
它们有什么用?
借用Chris Ammerman的回答:Y-combinator泛化递归,抽象其实现,从而将其与函数的实际工作分离。
尽管Y-combinator有一些实际应用,但它主要是一个理论概念,理解它将扩展你的整体视野,并有可能提高你的分析和开发技能。
它们在过程语言中有用吗?
正如Mike Vanier所说:在许多静态类型的语言中都可以定义Y组合子,但是(至少在我看到的例子中)这样的定义通常需要一些不明显的类型技巧,因为Y组合子本身没有直接的静态类型。这超出了本文的范围,所以我不再进一步提及
正如Chris Ammerman所提到的:大多数过程式语言都有静态类型。
所以这个问题的答案是,不是真的。
如果你准备好长篇大论,Mike Vanier有一个很好的解释。长话短说,它允许您在一种不一定支持递归的语言中实现递归。
为了帮助自己掌握Y-Combinator,我在Clojure和Scheme中都写了一份关于Y-Combinator的“傻瓜指南”。他们受到了《小阴谋家》的影响
在方案: https://gist.github.com/z5h/238891
Clojure: https://gist.github.com/z5h/5102747
这两个教程都是代码中穿插的注释,应该剪切和粘贴到您最喜欢的编辑器。
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将发散/无限循环)。
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如何变魔术的完整解释,请查看链接文章(顺便说一下,不是我写的)。