Nodos con clave: ayudar a la comparación en listas que se reordenan

De todas las optimizaciones que se enseñan junto al DOM virtual, esta es la única que no es una optimización. Se presenta casi siempre en el capítulo de rendimiento, entre consejos sobre memoización y medición, y ese emplazamiento induce a tratarla como algo que se añade cuando el perfilador lo pide. Es un error de clasificación con consecuencias, porque una lista sin claves cuyos elementos se reordenan no produce solo lentitud: produce comportamiento incorrecto. El cursor salta de sitio mientras el usuario escribe, la selección de texto se pierde, un vídeo se reinicia, una animación empieza de nuevo, un componente personalizado olvida lo que sabía. Nada de eso se ve en un cronómetro y nada de eso aparece en pruebas automatizadas, porque ninguna prueba tiene el foco puesto en un campo mientras llega una actualización. Aparece en producción, lo cuenta un usuario con palabras que suenan inverosímiles, y sobrevive meses porque nadie consigue reproducirlo. Conviene por tanto invertir el orden habitual de la exposición: las claves no son una técnica para ir más rápido que se evalúa con mediciones, son la forma de comunicar al algoritmo una noción de identidad que no puede deducir del árbol, y su ausencia en una lista dinámica es un defecto que se corrige aunque el rendimiento sea perfecto.

Lo que ocurre paso a paso cuando falta la identidad

Imagina una lista de cien filas a la que se antepone un elemento nuevo. La comparación recorre ambos árboles en paralelo por posición: en el primer lugar encuentra la fila recién insertada frente a la que antes era la primera, y como ambas son elementos de la misma etiqueta no las sustituye, sino que baja a comparar sus atributos y su contenido y descubre que todo difiere. Repite lo mismo en la segunda posición, en la tercera y en las cien, y al llegar al final añade una fila más porque el árbol nuevo es más largo. El resultado es correcto en cuanto a lo que se ve, y el trabajo realizado es proporcional a la longitud de la lista cuando debería haber sido una sola inserción.

Conviene notar que el algoritmo no ha hecho nada incorrecto ni ha aplicado una heurística mala. Ha hecho exactamente lo único que podía hacer con la información disponible, que era comparar por posición porque la posición es lo único que distingue a un hijo de otro cuando nadie ha dicho otra cosa. El fallo no está en la comparación sino en la descripción, a la que le falta un dato, y por eso la corrección no consiste en cambiar el algoritmo sino en completar lo que se le entrega.

El daño en corrección es de otra naturaleza y no depende del tamaño. Cada fila cuyo contenido se reescribe pierde todo lo que el documento guardaba por su cuenta sobre ella. Esa lista es más larga de lo que suele recordarse y merece enunciarse entera, porque cada elemento de la lista es una categoría de fallo intermitente distinta.

Cómo empareja un contenedor con clave

La solución consiste en aportar la información que falta. Un contenedor con clave no recibe una lista de hijos sino una lista de pares formados por una cadena identificadora y el nodo correspondiente. Con eso, la comparación abandona el recorrido posicional para esa lista y empareja por clave: recorre ambas secuencias manteniendo índices en las dos, y en cada paso decide entre cuatro operaciones. Si las claves coinciden, compara ese par de nodos y avanza. Si la clave nueva aparece más adelante en la vieja, deduce una eliminación. Si la clave vieja aparece más adelante en la nueva, deduce una inserción. Y si las dos siguientes están cruzadas, deduce un intercambio y mueve el nodo real sin reconstruirlo.

import Html.Keyed as Keyed


listaTareas : Filtro -> List Tarea -> Html Msg
listaTareas filtro tareas =
    Keyed.node "ul" [ class "lista" ] (List.map conClave (visibles filtro tareas))


conClave : Tarea -> ( String, Html Msg )
conClave tarea =
    ( String.fromInt tarea.id, fila tarea )


-- Atajos para los contenedores habituales
-- Keyed.ul : List (Attribute msg) -> List ( String, Html msg ) -> Html msg
-- Keyed.ol : List (Attribute msg) -> List ( String, Html msg ) -> Html msg

Ese emparejamiento resuelve bien los casos que aparecen en la práctica —añadir al principio o al final, borrar del medio, intercambiar dos vecinos, mover un elemento unos pocos puestos— y para permutaciones arbitrarias recurre a insertar y eliminar allí donde no consigue reconocer un movimiento. No garantiza el número mínimo teórico de operaciones, que sería mucho más caro de calcular, pero sí garantiza lo que de verdad importa: que un nodo real reconocido por su clave se mueve en lugar de destruirse.

Los requisitos de una clave son dos y ambos se derivan del algoritmo anterior. Estable significa que el mismo elemento conserva su clave a lo largo del tiempo aunque cambie de sitio o de contenido, porque de eso depende que se lo reconozca al reaparecer en otra posición. Única dentro del contenedor significa que dos hijos no comparten clave, porque el emparejamiento se vuelve ambiguo y el resultado deja de ser predecible; el compilador no puede detectarlo, ya que la unicidad es una propiedad de los datos y no del tipo, así que la responsabilidad es del programador. Cuando el dato no trae identificador propio, generarlo al crearlo y guardarlo en el modelo es preferible a derivarlo del contenido, que puede repetirse y que además cambia cuando el contenido cambia, es decir, justo cuando la estabilidad haría falta.

Alcance, coste y el paralelo con React

Antes de bajar al detalle conviene fijar una consecuencia de diseño que se deduce de lo anterior y que decide la calidad de todo lo demás. Si la identidad tiene que ser estable, el sitio donde debe nacer es el modelo, en el momento en que el elemento se crea, y no la vista, en el momento en que se dibuja. Un identificador asignado al insertar el dato y conservado mientras el dato exista cumple los dos requisitos por construcción; cualquier cosa derivada en la vista —un resumen del contenido, una concatenación de campos, una posición— depende de aspectos que cambian justo cuando la identidad haría falta. La regla es que la clave debe ser un campo del dato, no un cálculo sobre él.

El alcance de las claves es un solo nivel: actúan entre los hijos directos del contenedor que las declara y no se propagan hacia abajo. Una estructura de grupos que contienen listas necesita claves en el nivel de los grupos y en el de cada lista interna, y poner solo las de arriba deja los reordenamientos internos exactamente igual que antes. Conviene además saber que un contenedor con clave es una forma de nodo distinta de un contenedor normal, de modo que convertir uno en otro entre dos dibujados provoca la sustitución de la rama completa; no es un problema en la práctica, porque nadie alterna, pero explica un caso desconcertante cuando la elección depende de una condición.

flowchart TD
L[Comparar dos listas] --> K[El contenedor declara claves]
K -->|No| P[Emparejar por posicion]
P --> X[Reescribir el contenido de todas las filas]
X --> Y[Se pierde foco seleccion y desplazamiento]
K -->|Si| Q[Emparejar por clave]
Q --> I[Insertar solo lo nuevo]
Q --> B[Eliminar solo lo que se fue]
Q --> M[Mover los nodos reales que siguen vivos]
style K fill:#89b4fa,color:#11111b
style Q fill:#a6e3a1,color:#11111b
style Y fill:#f38ba8,color:#11111b

El paralelo con React es directo y por eso conviene delimitar dónde termina. La idea es la misma, el problema que resuelve es el mismo y el error del índice es idéntico en ambos. Las diferencias son tres. La primera es sintáctica pero significativa: allí la clave es un atributo que se pone en cada hijo y aquí es parte del tipo del contenedor, que exige una lista de pares, de modo que olvidar una clave es un error de compilación en lugar de una omisión silenciosa. La segunda es que allí la clave puede ser un número o una cadena y aquí es siempre una cadena. La tercera es la más profunda: en React reconstruir un nodo destruye además el estado local de los componentes que contenga, porque los componentes tienen estado propio, mientras que en Elm todo el estado declarado vive en el modelo y solo se pierde el que el documento guarda por su cuenta. La consecuencia es que el daño por falta de claves es menor en Elm, aunque sigue siendo real y sigue siendo el género de fallo más difícil de reproducir.

El coste tampoco es nulo y conviene decirlo con claridad para no caer en el extremo contrario. Emparejar por clave exige construir la lista de pares, comparar cadenas y llevar la cuenta de qué se insertó y qué se eliminó, todo lo cual es más caro que avanzar por posición. En una lista estática, cuyos elementos jamás cambian de sitio, las claves solo añaden trabajo. El criterio es sencillo y no requiere mediciones: si el conjunto de hijos puede crecer, encoger o reordenarse durante la vida de la pantalla, hacen falta; si es fijo, sobran.

Claves y memoización en la misma lista

Las dos herramientas de este nivel se combinan con naturalidad porque actúan en capas distintas y responden a preguntas distintas. La envoltura perezosa decide si hace falta volver a construir la descripción de la lista, comparando las entradas de la función que la produce; el contenedor con clave decide, una vez construida, cómo emparejar la descripción nueva con la anterior. La primera evita trabajo cuando nada relevante cambió; la segunda minimiza el trabajo y evita el daño cuando algo sí cambió. Aplicar solo una de las dos deja sin cubrir la mitad del problema, y aplicarlas en el orden equivocado no produce error alguno, simplemente no ahorra.

view : Model -> Html Msg
view model =
    div []
        [ barraFiltros model.filtro
        , lazy2 listaTareas model.filtro model.tareas
        ]


listaTareas : Filtro -> List Tarea -> Html Msg
listaTareas filtro tareas =
    Keyed.node "ul" [ class "lista" ] (List.map conClave (visibles filtro tareas))


conClave : Tarea -> ( String, Html Msg )
conClave tarea =
    -- Cada fila decide por su cuenta si hace falta reconstruirla
    ( String.fromInt tarea.id, lazy fila tarea )