Y-combinator如何以编程方式计算固定点？ [英] How does Y-combinator compute the fixed point programmatically?

问题描述

我相信我在数学上理解Y-combinator的概念：它返回给定函数 F 的固定点，因此 f = Y（ F）其中 f 满足 f == F（f）。

I believe I understand mathematically the idea of Y-combinator: it returns the fixed point of a given functional F, thus f = Y(F) where f satisfies f == F(f).

但我不明白实际的计算程序是如何实现的？

But I don't understand how it does the actual computation program wise?

让我们来看看javascript示例给予此处：

Let's take the javascript example given here:

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）部分遇到无限递归，我看不到任何终止案件都暗示在那里。然而，奇怪的确回来了。任何人都可以解释一下吗？

The part I don’t understand is how the computed_factorial function (the fixed point) actually get computed? By tracing the definition of Y, you’ll find it runs into a infinitely recursion at the x(x) part, I can't see any terminating case implied there. However, it strangely does return. Can anyone explain?

推荐答案

Y组合子是lambda演算中最有趣的现象之一。我怀疑它立即看到它，人们可以想出它的功能。

The Y combinator is one of the most interesting phenomenons in the lambda calculus. I doubt that right away seeing it, one can come up with an interpretation of it's functionality.

Y = f => (g => g(g))(g => n => f(g(g))(n));

想法是递归地运行lambda（匿名函数）。

The idea is to run a lambda (anonymous function) recursively.

嘿等一下..！如果你没有名字来引用一个函数并且首先在其中调用它，你究竟能做到这一点..？

Hey wait a minute..! How exactly you can do it if you don't have a name to reference a function and call it within itself in the first place..?

让我们一步一步地了解它的推导。我将使用箭头函数，如果您不熟悉它们，请按照此链接。它们非常简单。 x => x 表示 function（x）{return x;} 。 JS 这个关键字在箭头中有不同的含义，但根据这个主题，这是关于主题的。

Let's try to understand it's derivation step by step. I will use the arrow functions so if you are not familiar with them please follow this link. They are very simple. x => x means function(x){return x;}. The JS this keyword has a different meaning within the arrows but that's off topic as per this subject.

所以总是我们将使用阶乘函数，但我们将导出的Y组合子对所有递归函数都有效。

So as always we will go with the factorial function but the Y combinator that we will derive will be valid for all recursive functions.

阶乘函数可以简单地表示如下

A factorial function can simply be expressed as follows

var fa = n => n === 0 ? 1 : n*fa(n-1);
fa(5) // <- 120

但是我们不说想要递归地引用 fa 函数;相反，我们希望从假设版本的阶乘函数中推导出一个工作因子函数。什么是假设的因子函数？假设因子函数采用适当的阶乘函数并返回一个工作因子函数。如下所示

But say that we don't want to refer to the fa function recursively; instead we would like to derive a working factorial function from a hypothetical version of the factorial function. What's a hypothetical factorial function? The hypothetical factorial function takes a proper factorial function and returns us a working factorial function. Like the following

var fh = f => n => n === 0 ? 1 : n*f(n-1);

因此，如果我将 fa 函数传递给 fh 作为参数，它应该有效。喜欢;

So if i pass fa function to fh as an argument it shall work. Like;

fh(fa)(5); // <- 120

但是我们不想引用像<$这样的另一个因子函数c $ c> fa 因为我们已经排序在 fh 函数中定义了因子逻辑。然后我们想。 fh 在闭包中保留 f 参数并返回一个有效的因子函数（ n => ; n === 0？1：n * f（n-1））如果我向 fa 传递适当的阶乘函数。那么如果我把它传给它呢？快速尝试 fh（fh）（5）//< - NaN meh ..！

But we don't want to refer to another factorial function like fa since we have already "sort of" defined the factorial logic within the fh function. Then we think. fh keeps the f argument in closure and returns me a working factorial function (n => n === 0 ? 1 : n*f(n-1)) if i pass a proper factorial function to it like fa. So what if i pass itself to it; A quick try fh(fh)(5) // <- NaN meh..!

所以我们开始玩内在的功能。通常我会通过这一步但看到转换可能会有所帮助...所以让我们继续。我可以定义 fb 函数来返回一个函数，它接受两个参数，本身和因子计数 n

So we start playing with the inner function. Normally i would pass this step but it might be helpful to see the transformations... so lets continue. I can define the fb function to return me a function which takes two arguments, itself and factorial count n

fb = (f,n) => n === 0 ? 1 : n* f(f,n-1), // fb(fb,5)  <- 120

到目前为止这么好但是两个论证因子函数并没有接近我正在寻找的东西。我可以通过添加另一个称为部分应用的功能步骤来分离它们。

So far so good but the two argument factorial function is no where close to what i am looking for. I can separate them by adding another functional step known as partial application.

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来帮助我们...

Now this is very close to our hypothetical function fh. But the inner shows f(f)(n-1) We have to correct this to show f(n-1). Well may be we can use a JS beauty IIFE to help us...

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才能达到预期的效果。这将通过部分申请获得另一个功能。

Can you see the IIFE..? ((g,n) => n === 0 ? 1 : n * g(n-1))(f(f),n) Yet, while this seems OK i have to get rid of the dual argument (g,n) IIFE to achieve the desired result. This will take another level of getting functional by partial application.

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 在上面的函数中读起来像;

Now we have inside g => n => n === 0 ? 1 : n * g(n-1) which is the body of our hypothetical function fh. Which means i can substitute (I love this part.. just like calculus substitution; in fact it is...) fh in the above function to read like;

fe = f => n => fh(f(f))(n) // fe(fe)(5)  <- 120

好的时候把它包起来。我首先想要的是什么......？我想将 fh 提供给一个函数（Y-combinator）并得到它的固定点。在这里我知道 fe（fe）使用 fh 并返回正确工作的因子函数。因此，我们定义一个函数，将我们的hyporthetical递归函数作为一个参数，并给我们一些工作（固定）。 IIFE再次提供帮助。

Ok time to wrap it up. What i have wanted in the first place..? I want to feed fh to a function (Y-combinator) and get it's fixed point. Here i know that fe(fe) uses fh and returns me the properly working factorial function. So lets define a function to take our hyporthetical recursive function as an argument and give us something working (fixed). IIFE to help again.

Y = f => (g => g(g))(g => n => f(g(g))(n));

所以这应该适用于任何事情。让我们用假设的Fibonacci函数来尝试我们的Y组合。

So this should work for anything. Let's try our Y combinator with a hypothetical Fibonacci function.

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));

我希望一切都清楚......

I hope it's all clear...

这篇关于Y-combinator如何以编程方式计算固定点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！