Scala中如何反转列表

Question

给定以下代码：

import scala.util.Random

object Reverser {

  // Fails for big list
  def reverseList[A](list : List[A]) : List[A] = {
    list match {
      case Nil => list
      case (x :: xs) => reverseList(xs) ::: List(x)
    }
  }

  // Works
  def reverseList2[A](list : List[A]) : List[A] = {
    def rlRec[A](result : List[A], list : List[A]) : List[A] = {
      list match {
        case Nil => result
        case (x :: xs) => { rlRec(x :: result, xs) }
      }
    }
    rlRec(Nil, list)
  }

  def main(args : Array[String]) : Unit = {
    val random = new Random
    val testList = (for (_ <- 1 to 2000000) yield (random.nextInt)).toList
    // val testListRev = reverseList(testList) <--- Fails
    val testListRev = reverseList2(testList)
    println(testList.head)
    println(testListRev.last)
  }
}

第一个版本的函数为什么在处理大输入时失败，而第二个版本可以正常工作。我怀疑这与尾递归有关，但我不是很确定。请问是否有人能够给我一个类似“白痴版”的解释呢？

- Andrei Ciobanu

---

为什么不使用 'val testListRev = testList.reverse'？ - Lutz

这个问题很久以前就被问过了，但是这里有你尾递归问题的答案。是的，这是由于尾递归优化。在你的第一个实现中，case (x :: xs) => reverseList(xs) ::: List(x)，在递归调用reverseList之后，程序必须将List(x)添加到其中。这意味着它不能被优化为一个循环，在你的第二个例子中：case (x :: xs) => { rlRec(x :: result, xs) } rlRec是最后一次调用，退出后没有其他操作，这就是为什么它不必为其创建新的堆栈帧。 - Luis Muñiz

Answer 1

好的，让我尝试用尾递归的方式来解释

如果你按照reverseList函数应该做的事情去做，你会得到：

reverseList(List(1,2,3, 4))
reverseList(List(2,3,4):::List(1)
(reverseList(List(3,4):::List(2)):::List(1)   
((reverseList(List(4):::List(3)):::List(2)):::List(1)
Nil:::List(4):::List(3):::List(2):::List(1)
List(4,3,2,1)

使用rlRec，您可以

rlRec(List(1,2,3,4), Nil)
rlRec(List(2,3,4), List(1))
rlREc(List(3,4), List(2,1))
rlRec(List(4), List(3,2,1))
rlRec(Nil, List(4,3,2,1))
List(4,3,2,1)

第一个实现和第二个实现的区别在于，第一个实现会让重写的过程变得越来越长。你需要记住在最后一个递归调用 reverseList 完成之后还要做什么事情：将元素添加到结果中。栈用于记住这一点。当这样做过度时，就会出现堆栈溢出。相反，使用 rlRec，重写始终具有相同的大小。当最后的 rlRec 完成时，结果可用。没有其他事情要做，没有需要记住的东西，也不需要使用栈。关键是，在 rlRec 中，递归调用是 return rlRec(something else)，而在 reverseList 中，它是return f(reverseList(somethingElse))，其中f为_ ::: List(x)。你需要记住你将不得不调用 f（这意味着也要记住x）（在 Scala 中不需要返回，只是为了清晰起见添加的。还请注意，val a = recursiveCall(x); doSomethingElse() 与 doSomethingElseWith(recursiveCall(x)) 是相同的，因此它不是尾部调用）。 当您具有递归尾调用时

def f(x1,...., xn)
    ...
    return f(y1, ...yn)
    ...

实际上没有必要记住第一个 f 的上下文，因为当第二个 f 返回时也不需要。因此它可以重写为：

def f(x1....xn)
start:
    ...
    x1 = y1, .... xn = yn
    goto start
    ...

这就是编译器所做的，因此您避免了堆栈溢出。

当然，函数f需要在某处有一个不是递归调用的返回。这就是由goto start创建的循环将退出的地方，就像递归调用序列停止的地方一样。

- Didier Dupont

Answer 2

如果一个函数在调用自身时是最后一步操作，那么它被称为尾递归。你可以通过添加@tailrec注解来检查函数是否为尾递归。

- 4e6

Answer 3

使用默认参数可以使您的尾递归版本与非尾递归版本一样简单，以便为结果提供初始值：

def reverseList[A](list : List[A], result: List[A] = Nil) : List[A] = list match {
  case Nil => result
  case (x :: xs) => reverseList(xs, x :: result)
}

虽然您可以像使用其他方法一样使用它，即reverseList(List(1,2,3,4))，但不幸的是，您正在使用可选的result参数暴露实现细节。目前似乎没有隐藏它的方法。这可能会让您感到担忧或者无所谓。

- Luigi Plinge

---

Scala的List类有一个名为reverse_:::的方法，几乎完美地实现了这个功能。文档描述了它的作用：“将给定列表的元素以相反的顺序添加到该列表的前面”。突然间，那个“额外”的参数成为了一个特性！我们可以使用someList reverse_::: Nil来反转它，或者使用someList reverse_::: otherList将someList倒置并添加到otherList的前面。通常情况下，通过对函数添加一个额外的参数来支持尾递归（称为累加器），你实际上是泛化了你的方法的目的。 - Ben

Answer 4

正如其他人所提到的，尾调用消除避免了在不需要时增加堆栈。如果您想知道优化的原理，可以运行

scalac -Xprint:tailcalls MyFile.scala

在消除阶段后，您可以显示编译器的中间表示形式。 （请注意，您可以在任何阶段之后执行此操作，并且可以使用scala -Xshow-phases打印阶段列表。）

例如，对于您的内部尾递归函数rlRec，它会给我：

def rlRec[A >: Nothing <: Any](result: List[A], list: List[A]): List[A] = {
  <synthetic> val _$this: $line2.$read.$iw.$iw.type = $iw.this;
  _rlRec(_$this,result,list){
    list match {
      case immutable.this.Nil => result
      case (hd: A, tl: List[A])collection.immutable.::[A]((x @ _), (xs @ _)) => _rlRec($iw.this, {
        <synthetic> val x$1: A = x;
        result.::[A](x$1)
      }, xs)
    }
  }
}

不用管那些合成的东西，重要的是 _rlRec 是一个标签（尽管它看起来像一个函数）。在模式匹配的第二个分支中对 _rlRec 的“调用”将被编译为字节码中的跳转。

- Philippe

Answer 5

第一种方法不是尾递归。请见：

case (x :: xs) => reverseList(xs) ::: List(x)

最后一次调用的是:::，而不是递归调用reverseList。另一个是尾递归。

- jpalecek

Answer 6

def reverse(n: List[Int]): List[Int] = {
  var a = n
  var b: List[Int] = List()
  while (a.length != 0) {
    b = a.head :: b
    a = a.tail
  }
  b
}

当您调用该函数时，请按以下方式调用：

reverse(List(1,2,3,4,5,6))

然后它会给出类似这样的答案，

res0: List[Int] = List(6, 5, 4, 3, 2, 1)

- Lahiru Mirihagoda