scala - 解释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.StackOverflowError
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)

Answer 1

首先，请注意这不是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))。我们调用事实(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分支，并且仅在那一点才会对求值。没过由于您的Y传入了comp()作为参数f，因此我们将再次进入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()方法，该方法返回一个简单的square()函数(即一个计算数字平方的函数)。代替直接返回square(x)，我们可以返回一个带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

希望这可以帮助。