lista inversa Scala

Question

Dado el siguiente código:

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

¿Por qué la primera versión de la función falla (por grandes entradas), mientras que la segunda variante funciona. Sospecho que es algo relacionado con la recursividad de la cola, pero no estoy muy seguro. ¿Puede alguien darme una explicación "para tontos"?

Answer 1

Ok voy a tratar recursión de cola para los maniquíes

Si sigue lo que tiene que hacer con reverseList, obtendrá

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, tiene

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) 

El La diferencia es que en el primer caso, la reescritura se hace cada vez más larga. Debe recordar qué hacer después de que se complete la última llamada recursiva al reverseList: elementos para agregar al resultado. La pila se usa para recordar eso. Cuando esto va demasiado lejos, obtienes un desbordamiento de pila. Por el contrario, con rlRec, la reescritura tiene el mismo tamaño todo el tiempo. Cuando finaliza el último rlRec, el resultado está disponible. No hay nada más que hacer, nada que recordar, no hay necesidad de la pila. La clave es que en rlRec, la llamada recursiva es return rlRec(something else), mientras que en reverseList es return f(reverseList(somethingElse)), con vagando _ ::: List(x). Es necesario recordar que tendrá que llamar a f (lo que implica recordar x también) (retorno no es necesario en Scala, acaba de agregar para mayor claridad. También tenga en cuenta que val a = recursiveCall(x); doSomethingElse() es lo mismo que doSomethingElseWith(recursiveCall(x)), por lo que no es una llamada de cola)

cuando tiene una llamada recursiva cola

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

en realidad no hay necesidad de recordar el contexto de la primera f para cuando el segundo volverá. Por lo tanto, se puede reescribir

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

Eso es lo que hace el compilador, por lo tanto, se evita el desbordamiento de pila.

Por supuesto, la función f necesita tener un retorno en alguna parte que no sea una llamada recursiva. Ahí es donde saldrá el ciclo creado por goto start, tal como es donde se detiene la serie de llamadas recursivas.

Answer 2

El primer método no es la cola recursiva. Ver:

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

La última operación invocada es :::, no la llamada recursiva reverseList. El otro es cola recursiva.

Answer 3

La función se llama tail recursive cuando se llama a sí misma como su última acción. Puede verificar si la función es tail recursive agregando la anotación @tailrec.

Answer 4

Como han mencionado otros, la eliminación de llamadas de cola evita el crecimiento de la pila cuando no es necesaria. Si tiene curiosidad acerca de lo que hace la optimización, puede ejecutar

scalac -Xprint:tailcalls MyFile.scala 

...para mostrar la representación intermedia del compilador después de la fase de eliminación. (. Tenga en cuenta que usted puede hacer esto después de cualquiera de las fases, y se puede imprimir la lista de fases con scala -Xshow-fases)

Por ejemplo, para su recursiva de cola función interna, rlRec, me da:

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

No importa qué cosas sintéticas, lo que importa es que _rlRec es una etiqueta (aunque parezca una función), y la "llamada" a _rlRec en la segunda rama de la coincidencia de patrones se compilará como un salto en bytecode.

Answer 5

Usted puede hacer su versión recursiva de cola tan simple como la versión no recursiva de cola mediante el uso de un argumento predeterminado para dar un valor inicial para los resultados:

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

Aunque puede utilizar esta de la misma manera que los demás, es decir, reverseList(List(1,2,3,4)), lamentablemente está exponiendo un detalle de implementación con el parámetro opcional result. Actualmente no parece haber una manera de ocultarlo. Esto puede o no preocuparte.

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 
} 

Cuando se llama a la función llama así,

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

entonces se dará respuesta como esta,

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