9

这是 Scala 中 Y-combinator 的实现：

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了，在执行过程中又是如何出来的？

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

3 回答 3

9

首先，请注意这不是 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 作为参数 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 （您可以在此处阅读有关它的更多信息）。

这是 eta-expansion 的另一个简单示例：假设我们有一个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

希望这可以帮助。

于 2016-01-31T13:15:02.907 回答
1

补充接受的答案，

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

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

鉴于此，我从 Rosetta 代码中复制了以下实现，该代码使用某种类型的技巧来实现 Y 组合器，而无需显式递归。看这里

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

希望这有助于理解。

于 2020-03-21T15:02:52.127 回答
0

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

于 2016-01-14T00:34:29.790 回答