反向列表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)
  }
}

为什么第一个版本的函数失败(对于大输入),而第二个版本的作用.我怀疑它与尾递归有关,但我不太确定.有人可以给我"傻瓜"的解释吗？

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)),同时具有fbeging _ ::: List(x).你需要记住你将不得不打电话f(这也意味着要记住x)(scala中不需要返回,只是为了清晰起见而添加.另请注意,它 val a = recursiveCall(x); doSomethingElse()是相同的doSomethingElseWith(recursiveCall(x)),因此它不是尾调用)

当你有一个递归尾调用

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

实际上f,当第二个返回时,实际上不需要记住第一个的上下文.所以它可以重写

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

这就是编译器的作用,因此可以避免堆栈溢出.

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

Answer 2

tail recursive当函数将其自身称为最后一个操作时,将调用该函数.您可以tail recursive通过添加@tailrec注释来检查功能是否正常.

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参数公开了实现细节.目前似乎没有办法隐藏它.这可能会或可能不会让您担心.

Answer 4

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

scalac -Xprint:tailcalls MyFile.scala

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

例如,对于你的内部,尾递归函数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的"调用"将被编译为字节码中的跳转.

Answer 5

第一种方法不是尾递归.看到:

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

调用的最后一个操作是:::,而不是递归调用reverseList.另一个是尾递归.