scala 反向列表Scala

Reverse list Scala

提问by Andrei Ciobanu

Given the following code:

鉴于以下代码：

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

Why the first version of the function fails (for big inputs), while the second variant works . I suspect it's something related to tail recursion, but I am not very sure . Can somebody please give me "for dummies" explanation ?

为什么函数的第一个版本失败（对于大输入），而第二个变体有效。我怀疑这与尾递归有关，但我不太确定。有人可以给我“傻瓜”解释吗？

回答by Didier Dupont

Ok let me try tail recursion for dummies

好的，让我为傻瓜尝试尾递归

If you follow what has to be done with reverseList, you will get

如果您按照 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)

With rlRec, you have

使用 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)

The difference is that in first case, the rewriting keeps getting longer. You have to remember thing to do after the last recursive call to reverseListwill have completed: elements to add to the result. The stack is used to remember that. When this goes too far, you get a stack overflow. On the opposite, with rlRec, the rewriting has the same size all along. When the last rlReccompletes, the result is available. There is nothing else to do, nothing to remember, no need for the stack. The key is that in rlRec, the recursive call is return rlRec(something else)while in reverseListit is return f(reverseList(somethingElse)), with fbeging _ ::: List(x). You need to remember you will have to call f(which implies remembering xtoo) ( return not needed in scala, just added for clarity. Also note that val a = recursiveCall(x); doSomethingElse()is the same as doSomethingElseWith(recursiveCall(x)), so it is not a tail call)

不同的是，在第一种情况下，重写的时间越来越长。您必须记住在最后一次递归调用reverseListwill 完成后要做的事情：要添加到结果的元素。堆栈用于记住这一点。当这走得太远时，您会遇到堆栈溢出。相反，对于rlRec，重写始终具有相同的大小。当最后一个rlRec完成时，结果可用。没有别的事情要做，没有什么要记住的，不需要堆栈。关键是 in rlRec，递归调用是return rlRec(something else)while in reverseListit is return f(reverseList(somethingElse))， with fbegging _ ::: List(x)。您需要记住，您将不得不调用f（这也意味着要记住x）（在 Scala 中不需要 return，只是为了清楚起见而添加的。另请注意， val a = recursiveCall(x); doSomethingElse()与 相同doSomethingElseWith(recursiveCall(x))，所以它不是尾调用）

When you have a recursive tail call

当您有递归尾调用时

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

there is actually no need to remember the context of the first ffor when the second one will return. So it can be rewritten

实际上没有必要记住第一个的上下文，f以便第二个何时返回。所以可以改写

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

That is what the compiler does, hence you avoid the stack overflow.

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

Of course, function fneeds to have a return somewhere which is not a recursive call. That is where the loop created by goto startwill exit, just as it is where the recursive calls series stops.

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

回答by 4e6

Function is called tail recursivewhen it call itself as it's last action. You can check if the function is tail recursiveby adding @tailrecannotation.

函数tail recursive在调用自身作为最后一个动作时被调用。您可以tail recursive通过添加@tailrec注释来检查该函数是否为。

回答by Luigi Plinge

You can make your tail-recursive version as simple as the non-tail-recursive version by using a default argumentto give an initial value for the results:

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

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

Although you can use this in the same way as the others, i.e. reverseList(List(1,2,3,4)), unfortunately you're exposing an implementation detail with the optional resultparameter. Currently there doesn't seem to be a way to hide it. This may or may not worry you.

尽管您可以以与其他方式相同的方式使用它，即reverseList(List(1,2,3,4))，不幸的是，您使用可选result参数公开了一个实现细节。目前似乎没有办法隐藏它。这可能会也可能不会让您担心。

回答by Philippe

As others have mentioned, tail-call elimination avoids growing the stack when it is not needed. If you're curious about what the optimization does, you can run

正如其他人提到的，尾调用消除避免在不需要时增加堆栈。如果您对优化的作用感到好奇，您可以运行

scalac -Xprint:tailcalls MyFile.scala

...to show the compiler intermediate representation after the elimination phase. (Note that you can do this after any phase, and you can print the list of phases with scala -Xshow-phases.)

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

For instance, for your inner, tail-recursive function rlRec, it gives me:

例如，对于你的内部尾递归函数 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: A = x;
        result.::[A](x)
      }, xs)
    }
  }
}

Nevermind there synthetic stuff, what matters is that _rlRec is a label (even though it looks like a function), and the "call" to _rlRec in the second branch of the pattern-matching is going to be compiled as a jump in bytecode.

没关系合成的东西，重要的是 _rlRec 是一个标签（即使它看起来像一个函数），并且模式匹配的第二个分支中对 _rlRec 的“调用”将被编译为字节码中的跳转。

回答by jpalecek

The first method is not tail recursive. See:

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

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

The last operation invoked is :::, not the recursive call reverseList. The other one is tail recursive.

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

回答by Lahiru Mirihagoda

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
}

When you call the function call it like this,

当你调用函数时，像这样调用它，

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

then it will give answer like this,

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

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