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

这是 Y 组合器在 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

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)

and

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.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 的正确表达式，只是不是组合器。

因此，我们首先将计算阶乘的部分放入一个单独的函数中。我们可以称其为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))。我们调用fact(5)，它实际上是Y(comp)(5)，并且Y(comp)计算结果为comp(Y(comp))。这就是关键点：我们停在这里因为 comp 需要一个函数并且它直到需要时才对其进行评估。因此，运行时将 comp(Y(comp)) 视为 comp(???) 因为 Y(comp) 部分是一个函数，并且仅在需要时才会进行计算。

你知道 Scala 中的按值调用和按名称调用参数吗？如果您将参数声明为someFunction(x: Int)，一旦调用 someFunction 就会对其进行求值。但如果你将其声明为someFunction(x: => Int)，那么 x 不会立即求值，而是在使用它的时候求值。第二个调用是“按名称调用”，它基本上将 x 定义为“不接受任何内容并返回 Int 的函数”。因此，如果您传入 5，实际上是传入一个返回 5 的函数。通过这种方式，我们可以实现函数参数的惰性求值，因为函数是在使用时进行求值的。

因此，comp 中的参数 f 是一个函数，因此仅在需要时才对其进行求值，即位于 else 分支中。这就是为什么整个事情有效 - Y 可以创建一个无限的 func(func(func(func(…)))) 链，但该链是惰性的。仅在需要时才计算每个新链接。

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

Q2:

This

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

是这个的语法糖

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

这意味着我们将整个事情包装到一个函数中。我们这样做并没有失去任何东西，反而得到了。

我们得到了什么？嗯，这和上一个问题的答案是一样的；这样我们就可以实现这一点func(Y(func))仅在需要时才会评估，因为它包装在函数中。这样我们就可以避免无限循环。将（单参数）函数 f 展开为函数 x => f(x) 称为eta 扩展（你可以阅读更多相关内容here https://medium.com/@sinisalouc/on-method-invocations-or-what-exactly-is-eta-expansion-1019b37e010c#.u5gmoh126).

这是 eta 扩展的另一个简单示例：假设我们有一个方法getSquare()它返回一个简单的square()函数（即计算数字平方的函数）。我们可以返回一个接受 x 并返回 square(x) 的函数，而不是直接返回 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

希望这可以帮助。