反向列表斯卡拉

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)