解释一下 Scala 中 Y 组合器的实现？

Question

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

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

Q1：结果120是怎么出来的，一步一步来的？因为Y(func)定义为func(Y(func))，所以Y应该越来越多，Y哪里丢了，120在peform过程中是怎么出来的？

Q2: 和

有什么区别

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?

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.WhosebugError
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)

Answer 1

我不知道答案，但会尝试猜测。因为你有 def Y[T](f: ...) = f(...) 编译器可以尝试用简单的 f 替换 Y(f)。这将创建 f(f(f(...))) 的无限序列。部分应用 f 您创建了一个新对象，并且这种替换变得不可能。

Answer 2

首先，请注意这不是 Y-组合子，因为该函数的 lambda 版本使用自由变量 Y。尽管它是 Y 的正确表达式, 只是不是组合子。

所以，让我们先把计算阶乘的部分放到一个单独的函数中。我们可以称它为 comp:

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

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

def fact = Y(comp)

Q1：

Y 定义为 func(Y(func))。我们调用实际上是 Y(comp)(5) 的 fact(5)，并且 Y(comp) 计算为 comp(Y(comp))。这是关键点：我们到此为止，因为 comp 需要一个函数，它直到需要时才计算它。因此，运行time 将 comp(Y(comp)) 视为 comp(???)，因为 Y(comp) 部分是一个函数，只有在（如果）需要时才会计算。

你知道 Scala 中的按值调用和按名称调用参数吗？如果您将参数声明为 someFunction(x: Int)，它会在调用 someFunction 时立即被评估。但是如果你把它声明为someFunction(x: => Int)，那么x不会马上被求值，而是在它被使用的那一点上。第二个调用是“按名称调用”，它基本上将您的 x 定义为“不接受任何内容并且 returns 是一个 Int 的函数”。所以如果你传入 5，你实际上传入了一个 returns 5 的函数。这样我们就实现了函数参数的惰性求值，因为函数是在它们被使用的时候求值的。

因此，comp 中的参数 f 是一个函数，因此仅在需要时才对其求值，这在 else 分支中。这就是整个事情起作用的原因——Y 可以创建无限的 func(func(func(func(…)))) 链，但链是惰性的。每个新的 link 仅在需要时计算。

因此，当您调用 fact(5) 时，它将运行通过正文进入 else 分支，并且 只有在那个点 f 才会被计算 。之前没有。由于您的 Y 作为参数 f 传入了 comp()，我们将再次深入研究 comp()。在 comp() 的递归调用中，我们将计算 4 的阶乘。然后我们将再次进入 comp 函数的 else 分支，从而有效地进入另一个递归级别（计算 3 的阶乘）。请注意，在每个函数调用中，您的 Y 都提供了一个 comp 作为 comp 的参数，但它仅在 else 分支中进行评估。一旦我们到达计算 0 的阶乘的级别，if 分支将被触发，我们将停止进一步向下。

Q2:

这个

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

是这个

的语法糖

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

这意味着我们将整个事情包装到一个函数中。这样做我们没有失去任何东西，只有收获。

我们收获了什么？好吧，这与上一个问题的答案中的技巧相同；通过这种方式，我们实现了 func(Y(func)) 只有在需要时才会被评估，因为它被包装在一个函数中。这样我们就可以避免无限循环。将（单参数）函数 f 扩展为函数 x => f(x) 称为 eta-expansion（您可以阅读更多相关信息 here）。

这是 eta 展开的另一个简单示例：假设我们有一个方法 getSquare()，其中 return 是一个简单的 square() 函数（即计算一个号码）。我们可以 return 一个接受 x 和 returns square(x):

的函数，而不是直接 returning 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

希望这对您有所帮助。

Answer 3

补充接受的答案，

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.

组合器不允许显式递归；它必须是没有自由变量的 lambda 表达式，这意味着它不能在其定义中引用自己的名称。在 lambda 演算中，不可能在函数体中引用函数的定义。递归只能通过传入一个函数作为参数来实现。

鉴于此，我从 rosetta 代码中复制了以下实现，该代码使用某种类型的技巧来实现 Y 组合子而无需显式递归。参见 here

  def Y[A, B](f: (A => B) => (A => B)): A => B = {
    case class W(wf: W => A => B) {
      def get: A => B =
        wf(this)
    }
    val g: W => A => B = w => a => f(w.get)(a)

    g(W(g))
  }

希望这有助于理解。

解释一下 Scala 中 Y 组合器的实现？

Explain this implementation of the Y combinator in Scala?

scala

combinators

y-combinator