什么是y-组合器？
y-combinator是从事物的“function”方面的comp-sci概念。 如果他们甚至听说过他们，大多数程序员对他们所知甚less。
什么是y-组合器？ 他们如何工作？ 他们有什么好处？ 它们在程序语言中有用吗？
如果你准备好长时间阅读， Mike Vanier有一个很好的解释 。 长话短说，它允许你用一种不一定支持它的语言实现recursion。
Y-combinator是一个“function性”（一种对其他function进行操作的function），当你不能从其内部引用function时，它可以进行recursion。 在计算机科学理论中，它概括recursion ，抽象它的实现，从而将其与实际的function分开。 不需要recursion函数的编译时名称的好处是一种奖金。 =）
这适用于支持lambda函数的语言。 lambda expression式的本质通常意味着他们不能通过名字来引用自己。 并且通过声明variables的方式来解决这个问题，引用它，然后分配lambdaexpression式来完成自我引用循环，是脆弱的。 可以复制lambdavariables，并重新分配原始variables，从而中断自引用。
Y-组合器在执行静态types语言（通常是过程式语言）时经常使用，因为通常在input限制时需要在编译时知道有关函数的参数个数。 这意味着必须为任何需要使用的参数计数写一个y组合器。
下面是一个如何在C＃中使用和使用Y-Combinator的例子。
使用Y-combinator涉及构buildrecursion函数的“非常规”方式。 首先，你必须把你的函数写成一段调用预先存在的函数的代码，而不是自己：
// Factorial, if func does the same thing as this bit of code... x == 0 ? 1: x * func(x - 1); 然后你把它变成一个函数来调用一个函数，然后返回一个这样做的函数。 这被称为function性的，因为它需要一个function，并执行一个操作，导致另一个function。
// A function that creates a factorial, but only if you pass in // a function that does what the inner function is doing. Func<Func<Double, Double>, Func<Double, Double>> fact = (recurs) => (x) => x == 0 ? 1 : x * recurs(x - 1);
现在你有一个函数，它接受一个函数，并返回另一个类似于阶乘函数的函数，而不是调用自身，而是调用传递给外部函数的参数。 你如何使这个因子？ 把内在的function传递给自己。 Y-Combinator通过一个具有永久名称的函数来实现这一点，它可以引入recursion。
// One-argument Y-Combinator. public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F) { return t => // A function that... F( // Calls the factorial creator, passing in... Y(F) // The result of this same Y-combinator function call... // (Here is where the recursion is introduced.) ) (t); // And passes the argument into the work function. }
而不是阶乘调用本身，会发生的是，阶乘调用阶乘生成器（通过recursion调用Y-Combinator返回）。 根据t的当前值，从发生器返回的函数将再次调用生成器，使用t – 1，或者返回1，结束recursion。
它是复杂而神秘的，但它在运行时全部被震撼，其工作的关键是“延迟执行”，并且recursion的分解跨越了两个function。 内部F 作为parameter passing ， 只有在必要时才会在下一次迭代中调用。
我从http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html取消了这个，这是我几年前写的一个解释。;
在这个例子中，我将使用JavaScript，但其他许多语言也可以使用。
我们的目标是能够仅使用1个variables和不分配的函数来编写1个variables的recursion函数，通过名称来定义事物等。（为什么这是我们的目标是另一个问题，让我们把这个作为我们的挑战'给予。）似乎不可能，嗯？ 作为一个例子，我们来实现阶乘。
那么第一步就是说如果我们骗了一点，我们就可以轻易做到这一点。 使用2个variables和赋值的函数，我们至less可以避免使用赋值来设置recursion。
// 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 );
现在让我们来看看我们是否可以less花钱。 首先，我们正在使用任务，但我们不需要。 我们可以直接写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 );
但是我们使用2个variables的函数来获得1个variables的函数。 我们能解决吗？ 那么一个名叫Haskell Curry的聪明人就有一个巧妙的把戏，如果你有更好的高阶函数，那么你只需要1个variables的函数。 certificate是，你可以从2（或更多在一般情况下）variables的函数获得1variables与纯粹的机械文本转换，如下所示：
// Original F = function (i, j) { ... }; F(i,j); // Transformed F = function (i) { return function (j) { ... }}; F(i)(j);
在哪里…保持完全一样。 （这个技巧在发明者之后被称为“currying”，Haskell也是以Haskell Curry的名字命名的），现在只要把这个转换应用到任何地方，我们就可以得到我们的最终版本。
// 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（）返回，绑定到一个button，不pipe。 该代码recursion地计算阶乘，而不使用赋值，声明或2个variables的函数。 （但试图追踪它是如何工作的可能会使你的头脑旋转，而如果没有推导，只是稍微重新格式化就会导致代码难以理解和混淆。）
你可以用你想要的任何recursion函数来replacerecursion定义factorial的4行。
我想知道是否有什么用途试图从头开始build设。 让我们来看看。 这是一个基本的recursion阶乘函数：
function factorial(n) { return n == 0 ? 1 : n * factorial(n - 1); }
让我们重构并创build一个名为fact的新函数，它将返回一个匿名阶乘计算函数，而不是自己执行计算：
function fact() { return function(n) { return n == 0 ? 1 : n * fact()(n - 1); }; } var factorial = fact();
这有点奇怪，但没有错。 我们只是在每一步生成一个新的因子函数。
在这个阶段recursion还是相当明确的。 fact函数需要知道自己的名字。 让我们参数化recursion调用：
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);
这很好，但recurser仍然需要知道自己的名字。 让我们来参数化一下：
function recurser(f) { return fact(function(x) { return f(f)(x); }); } var factorial = recurser(recurser);
现在，不是直接调用recurser(recurser) ，而是创build一个返回结果的包装函数：
function Y() { return (function(f) { return f(f); })(recurser); } var factorial = Y();
我们现在可以完全摆脱recurser名称; 这只是Y的内部函数的一个参数，可以用函数本身来代替：
function Y() { return (function(f) { return f(f); })(function(f) { return fact(function(x) { return f(f)(x); }); }); } var factorial = Y();
仍然引用的唯一的外部名称是fact ，但现在应该清楚，这也很容易参数化，创build一个完整的通用解决scheme：
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-组合器是什么，但不是它是什么。
使用定点组合器来显示lambda演算已经完成 。 这是计算理论中非常重要的一个结果，为函数式编程提供了理论基础。
学习定点组合器也帮助我真正理解函数式编程。 但是我从来没有在实际编程中find任何用处。
JavaScript中的 y-combinator：
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
编辑 ：我从代码学习了很多东西，但这个有点难以吞下没有一些背景 – 对此感到遗憾。 通过其他答案提供的一些常识，您可以开始分辨正在发生的事情。
Y函数是“y-组合器”。 现在看一下使用Y的var factorial线。 注意你将一个函数传递给它，它有一个参数（在这个例子中是recurse ），这个参数也是稍后在内部函数中使用的。 参数名称基本上成为允许它执行recursion调用的内部函数的名称（因为它在它的定义中使用了recurse() ）。y-组合器执行将匿名内部函数与参数名称相关联的魔力函数传递给Y.
对于如何Y做魔术的完整解释，检查了链接的文章 （不是由我顺便说一句）。
对于没有深入了解函数式编程的程序员而言，现在并不在意从头开始，而是有点儿好奇：
Y组合器是一个公式，它允许您在函数不能有名称但可以作为parameter passing，用作返回值并在其他函数中定义的情况下实现recursion。
它通过将函数作为parameter passing给自己来工作，所以它可以调用自己。
它是lambda演算的一部分，它是真正的math，但实际上是一种编程语言，对计算机科学尤其是函数式编程非常重要。
Y组合器的日常实用价值是有限的，因为编程语言倾向于让你命名函数。
如果你需要在警察阵容中识别它，看起来像这样：
Y =λf。（λx.f（xx））（λx.f（xx））
你通常可以发现它，因为重复(λx.f (xx)) 。
λ符号是希腊字母lambda，它给出lambda演算的名称，并且有很多(λx.t)样式术语，因为这就是lambda演算的样子。
其他答案提供了相当简洁的答案，没有一个重要的事实：你不需要用这种复杂的方式来实现任何实际语言中的定点组合，这样做没有任何实际的目的（除了“看，我知道什么是Y-组合器是“）。 这是重要的理论概念，但实用价值不大。
Y型组合器是磁通电容器的另一个名称。
这里是Y-Combinator和Factorial函数的JavaScript实现（来自Douglas Crockford的文章，可在http://javascript.crockford.com/little.html上find ）。
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);
我在Clojure和Scheme中为Y-Combinator写了一个“白痴指南”，以帮助我自己去解决这个问题。 他们受到“小小的策士”中的材料的影响，
在计划： https ： //gist.github.com/z5h/238891
或Clojure： https ： //gist.github.com/z5h/5102747
这两个教程都是代码散布与评论，应该剪切和可编辑到您最喜爱的编辑器。
y组合器实现匿名recursion。 所以，而不是
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-组合器（y-组合器将发散/无限循环）。
定点组合器（或定点算子）是计算其他函数的固定点的高阶函数。 这个操作在编程语言理论中是相关的，因为它允许以重写规则的forms实现recursion，而不需要语言的运行时引擎的明确支持。 （src维基百科）
这个操作符可以简化你的生活：
var Y = function(f) { return (function(g) { return g(g); })(function(h) { return function() { return f.apply(h(h), arguments); }; }); };
那么你避免了额外的function：
var fac = Y(function(n) { return n == 0 ? 1 : n * this(n - 1); });
最后，你叫fac(5) 。
作为combinators的新手，我发现Mike Vanier的文章 （谢谢Nicholas Mancuso）非常有帮助。 我想写一个总结，除了logging我的理解，如果能帮到别人，我会很高兴的。
从蹩脚到不太蹩脚
以阶乘为例，我们使用下面的almost-factorial函数来计算x阶乘：
def almost-factorial fx = if iszero x then 1 else * x (f (- x 1))
在上面的伪代码中， almost-factorial取函数f和数x （ almost-factorial是curried的，所以可以看作函数f并返回一个一元函数）。
当almost-factorial计算x阶乘时，它将x - 1阶乘的计算委托给函数f并将结果与x累加（在这种情况下，它将（x-1）的结果乘以x）。
可以看作almost-factorial采用了一个糟糕的阶乘函数（它只能计算到x - 1 ），并返回一个不太糟糕的阶乘版本（计算到x数量）。 就像这样：
almost-factorial crappy-f = less-crappy-f
如果我们反复通过almost-factorial ，我们最终会得到我们期望的因子函数f 。 在哪里可以考虑为：
almost-factorial f = f
固定点
almost-factorial f = f的事实意味着f是函数的almost-factorial的固定点 。
这是看到上述function的关系的一个非常有趣的方式，这对我来说是一个麻烦的时刻。 （如果你还没有，请阅读Mike的文章）
三个function
为了推广，我们有一个非recursion函数fn （就像我们的几乎因子），我们有它的定点函数fr （就像我们的f），然后Y做的是当你给Y fn ， Y返回定点fnfunction
所以总的来说（通过假设fr只需要一个参数来简化; x退化为x - 1 ， x - 2 …）。
- 我们将核心计算定义为
fn：def fn fr x = ...accumulate x with result from (fr (- x 1))，这是几乎有用的函数 – 尽pipe我们不能直接在x上使用fn，很快有用。 这个非recursionfn使用函数fr来计算其结果 -
fn fr = fr，fr是fn的定点，fr是有用的函数，我们可以用fr来得到我们的结果 -
Y fn = fr，Y返回函数的固定点，Y将我们几乎有用的函数fn变成有用的fr
派生Y （不包括）
我将跳过Y的推导并去理解Y Mike Vainer的文章有很多细节。
Y的forms
Y被定义为（在lambda微积分格式中）：
Y f = λs.(f (ss)) λs.(f (ss))
如果我们replace函数左侧的variabless ，就可以得到
Y f = λs.(f (ss)) λs.(f (ss)) => f (λs.(f (ss)) λs.(f (ss))) => f (Y f)
所以确实， (Y f)的结果是(Y f)的定点。
为什么(Y f)有效？
根据f的签名， (Y f)可以是任何一个元的函数，为了简化，假设(Y f)只有一个参数，就像我们的阶乘函数一样。
def fn fr x = accumulate x (fr (- x 1))
自fn fr = fr以来，我们继续
=> accumulate x (fn fr (- x 1)) => accumulate x (accumulate (- x 1) (fr (- x 2))) => accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))
recursion计算在最内部(fn fr 1)是基本情况并且fn在计算中不使用fr时终止。
再看看Y ：
fr = Y fn = λs.(fn (ss)) λs.(fn (ss)) => fn (λs.(fn (ss)) λs.(fn (ss)))
所以
fr x = Y fn x = fn (λs.(fn (ss)) λs.(fn (ss))) x
对我来说，这个设置的神奇部分是：
-
fn和fr互相依赖：fn在内部，每当fr被用来计算x，它会'产生'（'lifts'？）一个fn并把计算委托给那个fn（传入fr和x）; 另一方面，fn依赖于fr并使用fr来计算较小问题x-1。 - 在
fr被用来定义fn（当fn在其操作中使用fr时），真正的fr还没有被定义。 - 它定义了真正的业务逻辑。 基于
fn，Y以特定forms创buildfr– 辅助函数 – 以recursion方式促进fn的计算。
现在这帮助我理解Y ，希望它有帮助。
顺便说一下，我还发现了这本书“通过Lambda微积分进行函数式编程的介绍”非常好，我只是通过它的一部分，而且在书中我无法理解Y的事实导致了我的这个职位。
我认为回答这个问题的最好方法是select一种语言，如JavaScript：
function factorial(num) { // If the number is less than 0, reject it. if (num < 0) { return -1; } // If the number is 0, its factorial is 1. else if (num == 0) { return 1; } // Otherwise, call this recursive procedure again. else { return (num * factorial(num - 1)); } }
现在重写它，使其不使用函数内的函数的名称，但仍然recursion地调用它。
函数名称factorial应该被看见的唯一的地方是在呼叫站点。
提示：你不能使用函数的名字，但是你可以使用参数的名字。
解决问题。 不要看它。 一旦你解决了，你就会明白y-combinator解决了什么问题。
n的阶乘fact可以被certificate
fact 0 = 1 fact n = n * fact (n - 1)
定点组合是根据定义满足等价性的高阶函数fix
fix f = f (fix f)
fix f表示对于定点方程x = fx解x = fx 。 使用fix ，可以导出一般/μrecursion函数的任意构造性certificate，而不具有不可否认的自指定性。
fact n = (fix fact') n
哪里
fact' rec n = if n == 0 then 1 else n * rec (n - 1)
这样
fact 3 = (fix fact') 3 = fact' (fix fact') 3 = if 3 == 0 then 1 else 3 * (fix fact') (3 - 1) = 3 * (fix fact') 2 = 3 * fact' (fix fact') 2 = 3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1) = 3 * 2 * (fix fact') 1 = 3 * 2 * fact' (fix fact') 1 = 3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1) = 3 * 2 * 1 * (fix fact') 0 = 3 * 2 * 1 * fact' (fix fact') 0 = 3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1) = 3 * 2 * 1 * 1 = 6
这个formscertificatefact 3 = 6有条件地使用定点组合等价来fix fact' => fact' (fix fact') 。 这样的过程被称为匿名recursion 。
无types的lambda微积分forms主要由上下文无关的语法组成
E ::= v Variable | λ v. E Abstraction | EE Application
其中v在variables上，以及beta和eta减less规则
(λ x. B) E => B[x := E] every free occurrence of x in B is substituted by E λ x. E x => E if x doesn't occur free in E
a在λ b. ba是自由的 λ b. ba λ b. ba ，但不在λ a. λ b. ba λ a. λ b. ba λ a. λ b. ba 。 Eta减less通常被省略。 两个缩减规则都不适用的expression式是正常的 ，或者也称为规范forms 。 λ x y. E λ x y. E是λx的简写λ x. λ y. E λ x. λ y. E λ x. λ y. E （多重性）， EFG是(EF) G （左结合性）的简写。 λ f x. fx λ f x. fx和λ g y. gy λ g y. gy是alpha-equivalent 。
数据，如数字，元组，布尔值，列表或树，对于无types的lambda演算来说不是原始的。 教会的数字是类似于Peano-axiomatic自然的自然数的编码 。 来自该编码的一些名称：
0 = λ f x. x No application 1 = λ f x. fx Single application 2 = λ f x. f (fx) Twofold 3 = λ f x. f (f (fx)) Threefold . . . SUCC = λ nf x. f (nfx) Successor ADD = λ nmf x. nf (mfx) Addition MULT = λ nmf x. n (mf) x Multiplication
一个正式的certificate， 1 + 2 = 3 ，使用单个重写规则的贝塔缩减：
ADD 1 2 = (λ nmf x. nf (mfx)) (λ g y. gy) (λ h z. h (hz)) = (λ mf x. (λ g y. gy) f (mfx)) (λ h z. h (hz)) = (λ mf x. f (mfx)) (λ h z. h (hz)) = λ f x. f ((λ h z. h (hz)) fx) = λ f x. f (f (fx)) Normal form = 3
在lambda微积分中， 组合器是不包含自由variables的抽象。 最简单的：I，身份组合器λ x. x λ x. x 。 这种组合器是SKI系统这样的组合器结石的原始操作者。
S = λ xy z. xz (yz) K = λ x y. x I = λ x. x
β减less不是很强的正常化 ; 并不是所有可还原的expression（“指数”）在β还原下都会收敛到正常forms。 一个简单的例子是omegaω组合器λ x. xx不同应用λ x. xx λ x. xx本身。
(λ x. xx) (λ y. yy) = (λ y. yy) (λ y. yy) Substitution for variable x . . . = ⊥ Divergence/"Bottom"
正常顺序优先减less应用程序最左边的子expression式（“头”）。 应用程序顺序在replace之前对参数进行规范化。 这两种策略分别类似于懒惰（如Miranda，Haskell）和渴望（如C，Scheme）评估。
(λ a b. a) ((λ i. i) n) ((λ x. xx) (λ y. yy))
在应用阶段缩小时不会收敛到正常forms：
(λ a b. a) ((λ i. i) n) ((λ x. xx) (λ y. yy)) = (λ a b. a) n ((λ x. xx) (λ y. yy)) Substitution for variable i = (λ a b. a) n ((λ y. yy) (λ y. yy)) For x . . . = ⊥ Bottom
但是，在正常顺序的beta缩减下：
(λ a b. a) ((λ i. i) n) ((λ x. xx) (λ y. yy)) = (λ b. ((λ i. i) n)) ((λ x. xx) (λ y. yy)) Substitution for a = (λ i. i) n For b = n For i; normal form
如果一个expression式具有一个正常forms，则正常顺序的β缩减将会find它。
Y定点组合器 λ f. (λ x. f (xx)) (λ x. f (xx)) λ f. (λ x. f (xx)) (λ x. f (xx))的基本性质：
Y g = (λ f. (λ x. f (xx)) (λ x. f (xx))) g = (λ x. g (xx)) (λ x. g (xx)) = Y g = g ((λ x. g (xx)) (λ x. g (xx))) = g (Y g) = g (g ((λ x. g (xx)) (λ x. g (xx)))) = g (g (Y g)) . . . . . .
Y g = g (Y g)同构于fix f = f (fix f) 。 无types的lambda演算可以在通用/μrecursion函数上编码任意的构造性certificate。
FACT = λ n. Y FACT' n FACT' = λ rec n. if n == 0 then 1 else n * rec (n - 1) FACT 3 = (λ n. Y FACT' n) 3 = Y FACT' 3 = FACT' (Y FACT') 3 FACT' for f = if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1) Y FACT' for rec, 3 for n = 3 * (Y FACT') (3 - 1) Boolean decision = 3 * FACT' (Y FACT') 2 FACT' for f = 3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1) . . . = 3 * 2 * (Y FACT') 1 = 3 * 2 * FACT' (Y FACT') 1 = 3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1) = 3 * 2 * 1 * (Y FACT') 0 = 3 * 2 * 1 * FACT' (Y FACT') 0 = 3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1) = 3 * 2 * 1 * 1 Delayed multiplication = 6 Normal form
正常的贝塔缩减使得无types的lambda演算成为一个图灵完整有效的 重写系统 。
对于Churchian无types的lambda微积分，已经certificate存在除了Y之外的recursion可枚举的无穷大的定点组合器。
X = λ f. (λ x. xx) (λ x. f (xx)) Y' = (λ x y. xyx) (λ y x. y (xyx)) Z = λ f. (λ x. f (λ v. xxv)) (λ x. f (λ v. xxv)) Θ = (λ x y. y (xxy)) (λ x y. y (xxy)) . . .
在Haskell中， fix可以被优雅地实现为
fix :: forall a. (a -> a) -> a fix f = f (fix f)
要么
fix f = let { x = fx; } in x
在评估所有子expression式之前，Haskell的懒惰会得到一个结果。
primes :: Integral a => [a] primes = sieve [2 ..] where sieve = fix (\ rec (p : ns) -> p : rec [n | n <- ns , n `rem` p /= 0])
- 教会的论文和function编程由大卫·特纳
- 阿朗佐教会初等数论的不可解决问题
