Y组合器如何以编程方式计算不动点
How does Y-combinator compute the fixed point programmatically?
我相信我在数学上理解Y-组合子的思想：它返回给定泛函F的不动点，从而f = Y(F) f满足f == 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)部分遇到了无限递归，我看不到那里暗示的任何终止案例。然而，奇怪的是，它确实回来了。谁能解释一下？
我将使用 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-组合器可以定义为：
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) )))
Y 组合子是 lambda 演算中最有趣的现象之一。我怀疑立即看到它，人们可以对它的功能做出解释。
Y = f => (g => g(g))(g => n => f(g(g))(n));
这个想法是递归运行一个lambda(匿名函数(。
嘿，等一下..！如果你没有一个名字来引用一个函数并首先在它里面调用它，你到底该怎么做..？
让我们试着一步一步地理解它的推导。我将使用箭头功能，因此如果您不熟悉它们，请点击此链接。它们非常简单。 x => x意味着function(x){return x;}。JS this关键字在箭头中具有不同的含义，但根据此主题，这是偏离主题的。
因此，与往常一样，我们将使用阶乘函数，但我们将导出的 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 参数闭包状态，如果我像 fa 一样将适当的阶乘函数传递给它，则返回一个工作阶乘函数 (n => n === 0 ? 1 : n*f(n-1)(。那么，如果我把自己交给它呢？快速尝试fh(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) 然而，虽然这似乎没问题，但我必须摆脱 IIFE (g,n)双重论点才能达到预期的结果。这将需要另一个级别通过部分应用程序获得功能。
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-组合器(并得到它的固定点。在这里我知道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));我希望一切都清楚了...
我想详细阐述(这将是一个很长的阅读(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)
让我们进入正题
整个评估(不工作(Y F 如下所示：
Y F -> 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((。因此，我们陷入了循环...Y F -> 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) )))
相反，评估类似于懒惰情况：
Y F -> 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(( 现在结束计算，因为这是匿名函数。这类似于第一个惰性计算。
- 为什么这在IE中的工作方式与在Firefox中不同
- 在AngularJS应用程序中使用封装指令和路由的推荐方式是什么
- Windows8应用程序(html&Javascript）:从图片库(除了文件选择器）显示图像的另一种方式
- 根据元素和容器大小计算边距
- 从Rally获取一个特定的标记，以便计算另一个字段中的值
- 在localhost Dev Box上测试JSONP请求的最佳方式
- 使用javascript存储变量的最安全方式
- 使用D3.js计算带有字母间距的文本长度
- Y组合器如何以编程方式计算不动点
- 以编程方式将fabric-js-canvas的图像替换为hq图像，并重新计算其他对象的坐标和大小
- true==false以某种方式计算为true
- 如何以用户友好的方式在计算机上保存从画布转换的图像
- JavaScript/jQuery:格式化日期计算结果的最佳方式
- 如何以编程方式计算两种颜色之间的对比度
- JavaScript-如何以编程方式计算颜色
- 为什么 (x += x += 1） 在 C 和 Javascript 中的计算方式不同
- 如何使用谷歌分析以准确和用户友好的方式计算传出链接
- 如何在AngularJS中以编程方式计算HTML元素(指令)的属性名
- 计算推特的Javascript字符数的最佳方式
- 使用html表单中的输入值进行计算的最佳方式是什么
