reverse con foldLeft: el acumulador que crece por el frenteLa función invierte una lista en una sola pasada y sin
recursión escrita a mano: toda la recursión está dentro de
foldLeft. Lo único propio es el valor inicial,
List[T](), y el operador (acc, x) => x :: acc.
Avance paso por paso y mire qué le pasa al acumulador en cada vuelta.
la lista que se recorre, de izquierda a derecha
el acumulador, con el elemento recién agregado en ámbar
El elemento en ámbar de la fila de arriba es el que la vuelta acaba de tomar; el de la fila de abajo es el mismo, ya puesto de cabeza en el acumulador. La línea 5 corre una sola vez, al final, y es la que devuelve el acumulador terminado.
Cada fila aparece cuando la ejecución llega a ese paso.
La inversión no está en ninguna línea que la
nombre. Sale de juntar dos hechos: foldLeft recorre la lista
del primer elemento al último, y :: agrega por el inicio. Cada
vuelta pone el elemento que acaba de leer delante de todos los anteriores,
así que el primero termina al fondo y el último de cabeza. La tabla lo deja
ver en la columna del acumulador: List(),
List(1), List(2, 1),
List(3, 2, 1).
El valor inicial decide qué devuelve la función cuando no hay elementos.
Con List[T](), la lista vacía entra por
case Nil => z y sale como List(), que es lo que
reverse(Nil) tiene que responder. Ese caso también cierra las
otras ejecuciones: la línea 5 corre una sola vez, cuando ya no queda
elemento, y entrega el acumulador sin tocarlo.
El costo es una pasada. Cada vuelta hace una sola operación,
x :: acc, que no recorre el acumulador porque solo agrega una
celda al frente, y hay tantas vueltas como elementos. Reconstruir la lista
con concatenaciones al final del acumulador recorrería lo ya acumulado en
cada paso, y ahí es donde aparece el comportamiento cuadrático que esta
versión evita.