Reverse lista Scala

Question

Dato il seguente codice:

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

Perché la prima versione della funzione fallisce (per i grandi ingressi), mentre la seconda variante funziona. Sospetto che si tratti di una ricorsione in coda, ma non ne sono molto sicuro. Qualcuno può darmi una spiegazione "per principianti"?

Answer 1

Ok farmi provare ricorsione di coda per i manichini

Se segui ciò che deve essere fatto con reverseList, si otterrà

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) 

Con rlRec, avete

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) 

Il la differenza è che nel primo caso, la riscrittura continua ad allungarsi. Devi ricordare cosa fare dopo che l'ultima chiamata ricorsiva a reverseList avrà completato: elementi da aggiungere al risultato. Lo stack è usato per ricordarlo. Quando questo va troppo lontano, ottieni uno stack overflow. Al contrario, con rlRec, la riscrittura ha sempre le stesse dimensioni. Al termine dell'ultimo rlRec, il risultato è disponibile. Non c'è nient'altro da fare, niente da ricordare, nessun bisogno di stack. La chiave è che in rlRec, la chiamata ricorsiva è return rlRec(something else) mentre in reverseList è return f(reverseList(somethingElse)), con f che inizia con _ ::: List(x). È necessario ricordare che si dovrà chiamare f (che implica ricordando x troppo) (ritorno non serve a Scala, appena aggiunto per chiarezza. Si noti inoltre che val a = recursiveCall(x); doSomethingElse() è lo stesso di doSomethingElseWith(recursiveCall(x)), quindi non è una chiamata di coda)

quando si ha una chiamata coda ricorsiva

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

v'è in realtà alcun bisogno di ricordare il contesto della prima f per quando il secondo tornerà. Quindi può essere riscritto

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

Questo è ciò che fa il compilatore, quindi si evita l'overflow dello stack.

Naturalmente, la funzione f deve avere un ritorno da qualche parte che non è una chiamata ricorsiva. È qui che si chiude il ciclo creato da goto start, proprio come è dove si ferma la serie di chiamate ricorsive.

Answer 2

Il primo metodo non è ricorsivo in coda. Vedi:

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

L'ultima operazione è invocato :::, non la chiamata ricorsiva reverseList. L'altro è coda ricorsiva.

Answer 3

La funzione si chiama tail recursive quando si chiama come ultima azione. È possibile verificare se la funzione è tail recursive aggiungendo l'annotazione @tailrec.

Answer 4

Come altri hanno già menzionato, l'eliminazione di coda evita di far crescere lo stack quando non è necessario. Se sei curioso di sapere cosa fa l'ottimizzazione, puoi eseguire

scalac -Xprint:tailcalls MyFile.scala 

...per mostrare la rappresentazione intermedia del compilatore dopo la fase di eliminazione. (. Si noti che è possibile farlo dopo ogni fase ed è possibile stampare l'elenco delle fasi con Scala -Xshow-fasi)

Per esempio, per il vostro interiore, coda ricorsiva funzione rlRec, mi dà:

Non importa che materiale sintetico, ciò che importa è che _rlRec è un'etichetta (anche se sembra una funzione) e la "chiamata" a _rlRec nel secondo ramo della corrispondenza del modello verrà compilata come un salto nel bytecode.

Answer 5

è possibile rendere la propria versione tail-ricorsiva semplice come la versione non-tail-ricorsiva utilizzando un argomento predefinito per dare un valore iniziale per i risultati:

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

Sebbene sia possibile utilizzare questo allo stesso modo degli altri, ovvero reverseList(List(1,2,3,4)), sfortunatamente stai esponendo un dettaglio di implementazione con il parametro opzionale result. Attualmente non sembra esserci un modo per nasconderlo. Questo potrebbe o non ti preoccupare.

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 
} 

Quando si chiama la funzione di chiamata in questo modo,

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

allora darà risposta in questo modo,

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