反向列表斯卡拉

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))，与f beging _ ::: 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

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

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

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

Answer 3

功能被称为tail recursive它称为自己的最后一个动作。您可以通过添加@tailrec注释来检查功能是否为tail recursive。

Answer 4

正如其他人已经提到的那样，tail-call消除避免了在不需要时增加堆栈。如果您对优化的内容感到好奇，您可以运行

scalac -Xprint:tailcalls MyFile.scala 

...在消除阶段之后显示编译器中间表示。 （请注意，您可以在任何阶段之后做到这一点，你可以使用Scala -Xshow-阶段打印阶段的列表）

例如，对于你的内心，尾递归函数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

可以使你的尾递归版本那么简单，通过使用默认参数给予对结果的初始值非尾递归版本：

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