construir: Nil, :: y las tres operaciones básicasToda lista se arma con dos piezas: Nil, que es
la lista vacía, y ::, que pone un elemento al frente de una
lista que ya existe. Las cuatro primeras líneas construyen
List(1, 2, 3), y el orden en que lo hacen no es el de la lista:
el 3 entra cuando todavía no hay nada detrás de él y el
1 entra de último. Las cinco últimas descomponen la lista de
frutas con head, tail e isEmpty.
Avance paso por paso y mire los dos valores que cambian: la lista que queda y
el elemento que la operación toma.
:: acaba de agregar
■ nodo que head devuelve
■ líneas de los selectores
El dibujo es la lista del chip lista: una
cadena de nodos donde cada uno guarda su elemento y apunta al siguiente, y
el último apunta a Nil. Los rótulos head y
tail.head marcan los dos primeros nodos. El contador de la
derecha de cada línea dice cuántas veces se evaluó.
:: no modifica la lista que recibe:
crea un nodo nuevo cuyo puntero apunta a la lista anterior. Por eso
paso2 sigue valiendo List(3) después de que
paso3 y paso4 se construyan, y por eso la
construcción avanza de derecha a izquierda. El 3 necesita que
Nil exista antes; el 1 necesita que exista
List(2, 3). Esa dependencia es la misma que hace que
:: se asocie a la derecha:
1 :: 2 :: 3 :: Nil se lee como
1 :: (2 :: (3 :: Nil)).
head y tail son las dos mitades de un nodo:
el primero devuelve el elemento que el nodo guarda, el segundo devuelve a
dónde apunta. Ninguno recorre la cadena, así que cuestan lo mismo con tres
elementos que con tres mil. Encadenarlos sí recorre:
frutas.tail.head son dos operaciones, y el contador de esa
línea llega a × 2.
head y tail sobre la lista vacía lanzan una
excepción, porque no hay nodo del que sacar nada:
NoSuchElementException y
UnsupportedOperationException. De ahí que
isEmpty se consulte antes de bajar por la cadena, o que el
descenso se escriba con match, que distingue las dos formas de
la lista sin preguntar.