解释Scala中Y组合器的这种实现? [英] Explain this implementation of the Y combinator in Scala?

问题描述

这是Scala中Y组合器的实现:

This is a implementation of the Y-combinator in Scala:

scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)
Y: [T](func: (T => T) => (T => T))T => T

scala> def fact = Y {
     |           f: (Int => Int) =>
     |             n: Int =>
     |               if(n <= 0) 1
     |               else n * f(n - 1)}
fact: Int => Int

scala> println(fact(5))
120

问题1:如何逐步得出结果120?因为Y(func)被定义为func(Y(func))，所以Y应该越来越多.Y在哪里消失了，120在形体成型过程中是如何出现的?

Q1: How does the result 120 come out, step by step? Because the Y(func) is defined as func(Y(func)), the Y should become more and more,Where is the Y gone lost and how is the 120 come out in the peform process?

Q2:两者之间有什么区别

Q2: What is the difference between

def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)

和

def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))

它们与scala REPL中的类型相同，但是第二个不能打印结果120?

They are the same type in the scala REPL, but the second one can not print the result 120?

scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))
Y: [T](func: (T => T) => (T => T))T => T

scala> def fact = Y {
     |           f: (Int => Int) =>
     |             n: Int =>
     |               if(n <= 0) 1
     |               else n * f(n - 1)}
fact: Int => Int

scala> println(fact(5))
java.lang.StackOverflowError
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)

推荐答案

首先，请注意，这不是Y- 组合器，因为该函数的lambda版本使用自由变量Y但是，它是Y的正确表达式，但不是组合器.

First of all, note that this is not a Y-combinator, since the lambda version of the function uses the free variable Y. It is the correct expression for Y though, just not a combinator.

因此，我们首先将计算阶乘的部分放入一个单独的函数中.我们可以称它为comp:

So, let’s first put the part which computes the factorial into a separate function. We can call it comp:

def comp(f: Int => Int) =
  (n: Int) => {
    if (n <= 0) 1
    else n * f(n - 1)
  }

阶乘函数现在可以这样构造:

The factorial function can now be constructed like this:

def fact = Y(comp)

第一季度:

Y定义为func(Y(func)).我们调用事实(5)，它实际上是Y(comp)(5)，并且Y(comp)的计算结果为comp(Y(comp)).这是关键点:我们在此处停止，因为comp具有功能，并且直到需要时才对其进行评估.因此，运行时将comp(Y(comp))视为comp(???)，因为Y(comp)部分是一个函数，并且仅在需要时才进行评估.

Y is defined as func(Y(func)). We invoke fact(5) which is actually Y(comp)(5), and Y(comp) evaluates to comp(Y(comp)). This is the key point: we stop here because comp takes a function and it doesn’t evaluate it until needed. So, the runtime sees comp(Y(comp)) as comp(???) because the Y(comp) part is a function and will be evaluated only when (if) needed.

您知道Scala中的按值致电和按姓名致电参数吗?如果将参数声明为someFunction(x: Int)，则将在调用someFunction时对其进行评估.但是，如果将其声明为someFunction(x: => Int)，则x不会立即进行评估，而是在使用该点时进行评估.第二个调用是按名称调用"，它基本上将x定义为不带任何内容并返回Int的函数".因此，如果传递5，则实际上传递的是返回5的函数.通过这种方式，我们实现了对函数参数的惰性求值，因为函数是在使用它们的那一点进行求值的.

Do you know about call-by-value and call-by-name parameters in Scala? If you declare your parameter as someFunction(x: Int), it will be evaluated as soon as someFunction is invoked. But if you declare it as someFunction(x: => Int), then x will not be evaluated right away, but at the point where it is used. Second call is "call by name" and it is basically defining your x as a "function that takes nothing and returns an Int". So if you pass in 5, you are actually passing in a function that returns 5. This way we achieve lazy evaluation of function parameters, because functions are evaluated at the point they are used.

因此，comp中的参数f是一个函数，因此仅在需要时才在else分支中求值.这就是为什么整个过程都起作用的原因-Y可以创建func(func(func(func(…)))))的无限链，但该链是惰性的.每个新链接仅在需要时计算.

So, parameter f in comp is a function, hence it is only evaluated when needed, which is in the else branch. That’s why the whole thing works - Y can create an infinite chain of func(func(func(func(…)))) but the chain is lazy. Each new link is computed only if needed.

因此，当您调用fact(5)时，它将贯穿正文进入else分支，并且仅在该点f会被评估.没过由于您的Y传入了comp()作为参数f，因此我们将再次进入comp().在comp()的递归调用中，我们将计算4的阶乘.然后，我们将再次进入comp函数的else分支，从而有效地跳入另一级递归(计算3的阶乘).请注意，在每个函数调用中，您的Y都提供了comp作为comp的参数，但仅在else分支中求值.一旦我们达到计算阶乘为0的水平，就会触发if分支，我们将停止进一步下潜.

So when you invoke fact(5), it will run through the body into the else branch and only at that point f will be evaluated. Not before. Since your Y passed in comp() as parameter f, we will dive into comp() again. In the recursive call of comp() we will be calculating the factorial of 4. We will then again go into the else branch of the comp function, thus effectively diving into another level of recursion (calculating factorial of 3). Note that in each function call your Y provided a comp as an argument to comp, but it is only evaluated in the else branch. Once we get to the level which calculates factorial of 0, the if branch will be triggered and we will stop diving further down.

第二季度:

此

func(Y(func))(_:T)

是语法糖

x => func(Y(func))(x)

这意味着我们将整个内容包装到一个函数中.通过这样做，我们没有损失任何东西，只有收获了.

which means we wrapped the whole thing into a function. We didn’t lose anything by doing this, only gained.

我们获得了什么?嗯，这和上一个问题的答案一样.这样，我们实现了func(Y(func))仅在需要时才被评估，因为它包装在函数中.这样我们将避免无限循环.将一个(单参数)函数f扩展为一个函数x => f(x)称为 eta-expansion (您可以详细了解

What did we gain? Well, it’s the same trick as in the answer to a previous question; this way we achieve that func(Y(func)) will be evaluated only if needed since it’s wrapped in a function. This way we will avoid an infinite loop. Expanding a (single-paramter) function f into a function x => f(x) is called eta-expansion (you can read more about it here).

这是eta展开的另一个简单示例:假设我们有一个方法getSquare()，该方法返回一个简单的square()函数(即计算数字平方的函数).除了直接返回square(x)之外，我们还可以返回一个接受x并返回square(x)的函数:

Here’s another simple example of eta-expansion: let’s say we have a method getSquare() which returns a simple square() function (that is, a function that calculates the square of a number). Instead of returning square(x) directly, we can return a function that takes x and returns square(x):

def square(x: Int) = x * x
val getSquare: Int => Int = square
val getSquare2: Int => Int = (x: Int) => square(x)

println(square(5)) // 25
println(getSquare(5)) // 25
println(getSquare2(5)) // 25

希望这会有所帮助.

这篇关于解释Scala中Y组合器的这种实现?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！