我相信我在数学上理解 Y-combinator 的概念：它返回给定函数 的不动点，F因此满足.f = Y(F)ff == F(f)
但我不明白它是如何明智地执行实际计算程序的？
让我们以这里给出的 javascript 示例为例：
var Y = (F) => ( x => F( y => x(x)(y) ) )( x => F( y => x(x)(y) ) )
var Factorial = (factorial) => (n => n == 0 ? 1 : n * factorial(n-1))
Y(Factorial)(6) == 720 // => true
computed_factorial = Y(Factorial)
我不明白的部分是computed_factorial函数（不动点）实际上是如何计算的？通过跟踪 Y 的定义，您会发现它在该部分遇到了无限递归x(x)，我看不到那里暗示任何终止情况。然而，它奇怪地确实回来了。谁能解释一下？
Y 组合子是 lambda 演算中最有趣的现象之一。我怀疑看到它后，人们能否对它的功能做出解释。
Y = f => (g => g(g))(g => n => f(g(g))(n));
这个想法是递归地运行一个 lambda（匿名函数）。
嘿等一下..！如果您没有名称来引用函数并首先在其自身内部调用它，那么您该怎么做呢？
让我们尝试一步一步地理解它的推导。我将使用箭头功能，所以如果您不熟悉它们，请点击此链接。它们非常简单。x => x意味着function(x){return x;}。JSthis关键字在箭头中具有不同的含义，但根据本主题，这是题外话。
因此，我们将一如既往地使用阶乘函数，但我们将推导出的 Y 组合子将适用于所有递归函数。
阶乘函数可以简单地表示如下
var fa = n => n === 0 ? 1 : n*fa(n-1);
fa(5) // <- 120
但是说我们不想fa递归地引用函数；相反，我们想从阶乘函数的假设版本中推导出一个有效的阶乘函数。什么是假设的阶乘函数？假设的阶乘函数采用适当的阶乘函数并返回给我们一个有效的阶乘函数。像下面这样
var fh = f => n => n === 0 ? 1 : n*f(n-1);
因此，如果我将fa函数fh作为参数传递给它，它将起作用。喜欢;
fh(fa)(5); // <- 120
但是我们不想引用另一个阶乘函数，fa因为我们已经“有点”在fh 函数中定义了阶乘逻辑。然后我们想。如果我将适当的阶乘函数传递给它，则将参数fh保持f在闭包中并返回一个工作阶乘函数（ ） 。那么如果我将自己传递给它呢？快速尝试咩..！n => n === 0 ? 1 : n*f(n-1)fafh(fh)(5) // <- NaN
所以我们开始玩内部函数。通常我会通过这一步，但看到转换可能会有所帮助......所以让我们继续吧。我可以定义fb函数来返回一个函数，它接受两个参数，它本身和阶乘计数n
fb = (f,n) => n === 0 ? 1 : n* f(f,n-1), // fb(fb,5) <- 120
到目前为止一切都很好，但是两个参数阶乘函数与我正在寻找的东西相去甚远。我可以通过添加另一个称为部分应用程序的功能步骤将它们分开。
fc = f => n => n === 0 ? 1 : n* f(f)(n-1), // fc(fc)(5) <- 120
现在这非常接近我们的假设函数fh。但是内部显示f(f)(n-1)我们必须更正它以显示 f(n-1)。好吧，也许我们可以使用一个 JS 美女 IIFE 来帮助我们......
fd = f => n => ((g,n) => n === 0 ? 1 : n * g(n-1))(f(f),n) // fd(fd)(5) <- 120
你能看到IIFE..吗？((g,n) => n === 0 ? 1 : n * g(n-1))(f(f),n)然而，虽然这看起来不错，但我必须摆脱双重参数(g,n)IIFE 才能达到预期的结果。这将通过部分应用获得另一个级别的功能。
fe = f => n => (g => n => n === 0 ? 1 : n * g(n-1))(f(f))(n) // fe(fe)(5) <- 120
现在我们有里面g => n => n === 0 ? 1 : n * g(n-1)是我们假设函数的主体fh。这意味着我可以在上面的函数中替换（我喜欢这部分..就像微积分替换；事实上它是......）fh
fe = f => n => fh(f(f))(n) // fe(fe)(5) <- 120
好的，是时候结束它了。我一开始想要什么..？我想输入fh一个函数（Y-combinator）并得到它的固定点。在这里我知道它fe(fe)使用fh并返回给我正常工作的阶乘函数。因此，让我们定义一个函数以将我们的假设递归函数作为参数并给我们一些工作（固定）的东西。IIFE 再次提供帮助。
Y = f => (g => g(g))(g => n => f(g(g))(n));
所以这应该适用于任何事情。让我们用假设的斐波那契函数来试试我们的 Y 组合器。
var Y = f => (g => g(g))(g => n => f(g(g))(n)),
fibH = f => n => n === 0 ? 0
: n === 1 ? 1
: f(n-2) + f(n-1),
fibo = Y(fibH);
console.log(fibo(10));我希望一切都清楚...
我将使用 ES6 箭头函数语法。由于您似乎了解 CoffeeScript，因此阅读它应该没有问题。
这是你的 Y 组合器
var Y = F=> (x=> F (y=> x (x) (y))) (x=> F (y=> x (x) (y)))
我将使用您的factorial功能的改进版本。这个使用累加器来代替，这将防止评估变成一个大金字塔。此函数的过程将是线性迭代的，而您的过程将是递归的。当 ES6 最终消除尾调用时，这会产生更大的不同。
语法上的差异是名义上的。无论如何，这并不重要，因为您只想看看如何Y评估 。
var factorial = Y (fact=> acc=> n=>
n < 2 ? acc : fact (acc*n) (n-1)
) (1);
那么这将导致计算机开始做一些工作。因此，在我们进一步讨论之前，让我们对此进行评估......
我希望你的文本编辑器中有一个非常好的括号荧光笔......
var factorial
= Y (f=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (1) // sub Y
= (F=> (x=> F (y=> x (x) (y))) (x=> F (y=> x (x) (y)))) (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (1) // apply F=> to fact=>
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (1) // apply x=> to x=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1) // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (1) // apply acc=> to 1
= n=> n < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*n) (n-1) // return value
= [Function] (n=> ...)
所以你可以在这里看到，在我们调用之后：
var factorial = Y(fact=> acc=> n=> ...) (1);
//=> [Function] (n=> ...)
我们得到一个等待单个输入的函数，n. 现在让我们运行一个阶乘
在我们继续之前，您可以通过在 javascript repl 中复制/粘贴来验证（并且应该）这里的每一行都是正确的。每一行都会返回
24（这是 . 的正确答案factorial(4)。对不起，如果我为你破坏了它）。这就像您在简化分数、求解代数方程或平衡化学公式时一样；每一步都应该是正确的答案。请务必一直滚动到右侧以查看我的评论。我告诉你我在每条线上完成了哪些操作。完成操作的结果在下一行。
并确保您再次方便地使用那个支架荧光笔......
factorial (4) // sub factorial
= (n=> n < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*n) (n-1)) (4) // apply n=> to 4
= 4 < 2 ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1) // 4 < 2
= false ? 1 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1) // ?:
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (1*4) (4-1) // 1*4
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (4-1) // 4-1
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (3) // apply y=> to 4
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (4) (3) // apply x=> to x=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4) (3) // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (4) (3) // apply acc=> to 4
= (n=> n < 2 ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*n) (n-1)) (3) // apply n=> to 3
= 3 < 2 ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1) // 3 < 2
= false ? 4 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1) // ?:
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (4*3) (3-1) // 4*2
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (3-1) // 3-1
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (2) // apply y=> to 12
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (12) (2) // apply x=> to y=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12) (2) // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (12) (2) // apply acc=> 12
= (n=> n < 2 ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*n) (n-1)) (2) // apply n=> 2
= 2 < 2 ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1) // 2 < 2
= false ? 12 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1) // ?:
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (12*2) (2-1) // 12*2
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (2-1) // 2-1
= (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (1) // apply y=> to 24
= (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (24) (1) // apply x=> to x=>
= (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24) (1) // apply fact=> to y=>
= (acc=> n=> n < 2 ? acc : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (acc*n) (n-1)) (24) (1) // apply acc=> to 24
= (n=> n < 2 ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*n) (n-1)) (1) // apply n=> to 1
= 1 < 2 ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*1) (1-1) // 1 < 2
= true ? 24 : (y=> (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (x=> (fact=> acc=> n=> n < 2 ? acc : fact (acc*n) (n-1)) (y=> x (x) (y))) (y)) (24*1) (1-1) // ?:
= 24
我也看到了其他的实现Y。这是一个从头开始构建另一个（用于javascript）的简单过程。
// text book
var Y = f=> f (Y (f))
// prevent immediate recursion (javascript is applicative order)
var Y = f=> f (x=> Y (f) (x))
// remove recursion using U combinator
var Y = U (h=> f=> f (x=> h (h) (f) (x)))
// given: U = f=> f (f)
var Y = (h=> f=> f (x=> h (h) (f) (x))) (h=> f=> f (x=> h (h) (f) (x)))
在惰性求值语言中，Y-combinator 可以定义为：
Y = (f =>
(x => f( x(x) ))
(x => f( x(x) )))
但是由于 Javascript 是一种急切的求值语言，以这种方式定义Y会导致x(x)部分在您尝试将Y应用于函数时无限期地递归。
为了解决这个问题，可以引入一个匿名的“包装器”函数来延迟x的执行。这个包装函数在调用时的行为与x(x)相同，但会立即返回，因为它只是一个函数定义。
在示例的情况下，知道x(x)将绑定到递归函数：
Factorial = f => n => n==0 ? 1 : n*f(n-1)
我们可以提前告诉它只有一个参数会传递给它。它允许我们使用以下模式来生成与任何给定函数f(x)行为相同的匿名函数：
f => x => f(x)
当我们将此模式应用于x(x)项时，Y将不再无限递归并变为：
Y = (f =>
(x => f( y => x(x)(y) ))
(x => f( y => x(x)(y) )))
我想详细说明（这将是一篇长篇文章）关于diwo关于渴望无限 x(x) 评估的答案。
在阅读了diwo的回答后，我很快浏览并跳过了不感兴趣的部分，下面是我对此的理解。
让我们用 x -> v 表示评估（程序的执行），意思是“x 评估为值 v”。
在急切和惰性求值中，匿名函数都被视为值，即它已经被求值，因此函数的求值立即停止。
然后对 f(y) 的急切求值将如下所示：f(y) -> (首先将 y 求值到 v) -> f(v) -> (将函数 f 应用于参数 v) -> f(v)。（现在（第二步之后）功能已真正应用，将在第二步中看到）
而相比之下，对 f(y) 的惰性求值会跳过第一步： f(y) -> (将函数 f 应用于参数 v) -> f(y) （现在函数已真正应用，但请注意，y 保持不变）。
现在让 F 是 Diwo 的答案中的阶乘，而 Y 是第一次定义的：
Y = (f =>
(x => f( x(x) ))
(x => f( x(x) )))
和
F = Factorial = f => n => n==0 ? 1 : n*f(n-1)
YF 的整个评估（不工作）如下所示：
YF -> w(w):= (x => F( x(x) ))(x => F( x(x) )) -> F( (x => F( x(x) ))( x => F( x(x) )) ) = F( w(w))，其中 w 是 (x => F( x(x) )) 的符号。现在这在急切和懒惰的评估中都是一样的，但从现在开始，我们得到了不同。
在惰性求值中，F 会“抽象地”（没有求值）应用于 w(w) 并且像这样求值
-> (n => n==0 ? 1 : n*(w(w))(n-1)) ) ,
然后它将停止评估，因为这是匿名函数，我们已经知道匿名函数不会被进一步评估。
在对对比度的渴望评估中，F(w(w)) -> F(v)，这意味着必须首先评估参数 w(w)。
现在计算 w(w) = (x => F( x(x) ))(x => F( x(x) )) -> F( (x => F( x(x) )) (x = > F( x(x) )) ) = F( w(w))。现在，在急切评估中，使用规则进一步评估首先评估参数，即 w(w)。正如我们刚刚看到的，它再次评估为 F(w(w))。因此我们陷入了循环... YF -> w(w) -> F(w(w)) -> F( F(w(w)) ) -> F( F(F(w(w)) ) ) -> ...错误。
如果我们通过定义来改进这一点
Y = (f =>
(x => f( y => x(x)(y) ))
(x => f( y => x(x)(y) )))
相反，评估类似于惰性情况：
YF -> z(z) := (x => F( y => x(x)(y) )) (x => F( y => x(x)(y) )) -> F( y => (x => F( y => x(x)(y) ))((x => F( y => x(x)(y) )))(y) )) = F( y = > z(z)(y)))。
作为急切的规则，我们现在必须评估参数（y => z(z)(y)）。因为这是匿名函数，所以它的评估是完整的，所以我们继续将 F 应用于 (y => z(z)(y) )，就像在惰性评估中一样。我们现在得到
F( y => z(z)(y) )) -> (n => n==0 ? 1 : n*(( y => z(z)(y) )(n-1)) ) 其中现在结束评估，因为这是匿名函数。这类似于第一次惰性求值。