← Volver a los ejercicios

reverse con foldLeft: el acumulador que crece por el frente

La 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.

1. La función y la ejecución

paso 0 de 0

la lista que se recorre, de izquierda a derecha

el acumulador, con el elemento recién agregado en ámbar

sin cerrar todavía

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.

2. La traza, fila por fila

Cada fila aparece cuando la ejecución llega a ese paso.

3. El orden del operador

4. Lo que se lleva de aquí

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.