Colecciones: List, Dict, Set y Array, y cuál merece estar en el Model · The Elm Architecture

Las cuatro lecciones anteriores han tratado de datos cuya forma se conoce al escribir el programa: un record tiene los campos que tiene y no puede tener otros. Pero ningún programa útil se limita a eso, porque tarde o temprano hay que guardar una cantidad de cosas que no se sabe de antemano, y esa cantidad puede crecer, menguar y reordenarse mientras la aplicación funciona. Elm ofrece cuatro estructuras para ese propósito, y elegir entre ellas es una decisión de modelado tan importante como elegir los campos del modelo, aunque casi siempre se toma sin pensar: List sale por defecto porque tiene sintaxis propia y porque es lo primero que se aprende, y ahí se queda. La consecuencia es previsible. Una aplicación que guarda entidades identificables en una lista acaba escribiendo, en cada rama de actualización, un recorrido completo para encontrar la que hay que cambiar, y esa forma de trabajar no falla nunca por corrección y falla siempre por claridad. Esta última lección del nivel pone las cuatro estructuras una al lado de otra, con su forma interna y sus costes, para que la elección deje de ser un reflejo y pase a ser una decisión.

🎯 Al terminar esta lección sabrás

Describir la estructura interna de List, Dict, Set y Array y deducir de ella sus operaciones baratas y caras.
Justificar por qué anteponer es barato en una lista y por qué añadir al final o indexar no lo son.
Elegir la colección adecuada según la operación dominante que la aplicación realiza sobre esos datos.
Combinar un diccionario de entidades con una lista de identificadores para separar la identidad del orden.

List: enlazada, inmutable y hecha para recorrerse

La lista de Elm es una lista simplemente enlazada: o está vacía, o es un elemento seguido de otra lista. De esa definición salen todos sus costes sin necesidad de medir nada. Anteponer es una operación de coste constante porque solo crea un eslabón nuevo que apunta a la lista anterior, que además se comparte entera. Cualquier operación que necesite llegar al final, en cambio, tiene que recorrerlo todo.

-- Anteponer es constante y comparte el resto de la lista
nuevos : List Int
nuevos =
    1 :: [ 2, 3, 4 ]

-- Recorrer es el modo natural de trabajar con listas
sumaPares : List Int -> Int
sumaPares =
    List.filter (\n -> modBy 2 n == 0)
        >> List.sum

-- Buscar por identidad obliga a recorrer, y devuelve Maybe
buscar : Int -> List Usuario -> Maybe Usuario
buscar id =
    List.filter (\u -> u.id == id)
        >> List.head

Que no exista acceso por índice no es una omisión: en una estructura enlazada, obtener el elemento de la posición n cuesta lo mismo que recorrer n elementos, de modo que ofrecer esa operación con sintaxis cómoda induciría a escribir bucles de coste cuadrático sin que nadie lo notara. Por eso la biblioteca empuja hacia map, filter y foldl, que recorren una sola vez. La lista es la elección correcta cuando el orden importa, cuando los elementos se procesan en bloque y cuando el acceso individual es raro.

ℹ️

Añadir al final es la trampa más común

Concatenar un elemento al final de una lista recorre la lista entera para reconstruirla, así que hacerlo dentro de un bucle produce un coste cuadrático que no se nota con veinte elementos y sí con veinte mil. El patrón idiomático consiste en anteponer siempre y, si el orden importa, invertir una única vez al terminar. Es exactamente lo que hace List.foldl por dentro, y la razón de que acumular con foldl y voltear al final sea más rápido que ir añadiendo por detrás.

Dict y Set: cuando la identidad manda

Un Dict asocia claves con valores y está implementado sobre un árbol binario equilibrado, lo que le da búsqueda, inserción y borrado en tiempo logarítmico, y un recorrido siempre ordenado por clave. A cambio impone una condición: la clave debe ser de un tipo comparable, es decir, un número, una cadena, un carácter, o una tupla o lista de ellos. Un Set es el mismo árbol sin valores, dedicado a pertenencia y unicidad.

type alias Model =
    { usuarios : Dict Int Usuario
    , seleccionados : Set Int
    }

-- Actualizar uno concreto no recorre la coleccion entera
renombrar : Int -> String -> Model -> Model
renombrar id nuevo modelo =
    { modelo
        | usuarios =
            Dict.update id (Maybe.map (\u -> { u | nombre = nuevo })) modelo.usuarios
    }

-- Pertenencia y unicidad, sin duplicados posibles por construccion
alternar : Int -> Set Int -> Set Int
alternar id conjunto =
    if Set.member id conjunto then
        Set.remove id conjunto

    else
        Set.insert id conjunto

La restricción de la clave comparable tiene una consecuencia práctica que sorprende: un identificador envuelto en un custom type, que es justo lo que la primera lección recomendaba para crear distinciones, no puede usarse como clave directamente. La salida habitual es guardar la clave desnuda en el diccionario y conservar el tipo envuelto en el resto del programa, desempaquetándolo solo en la frontera de acceso. Es una de las pocas grietas de ergonomía del lenguaje y conviene conocerla antes de tropezar con ella.

flowchart TD
Q{Como accedes a los datos} --> A[En bloque y en orden]
Q --> B[Por identidad]
Q --> C[Solo pertenencia]
Q --> D[Por posicion numerica]
A --> L[List]
B --> DI[Dict]
C --> S[Set]
D --> AR[Array]
style L fill:#a6e3a1,color:#11111b
style DI fill:#89b4fa,color:#11111b
style S fill:#cba6f7,color:#11111b
style AR fill:#f9e2af,color:#11111b

🔗

List

Enlazada. Anteponer es constante, recorrer es natural, indexar no existe. La opción por defecto cuando el orden manda.

🗝️

Dict

Árbol ordenado por clave comparable. Búsqueda y actualización logarítmicas. La casa natural de las entidades con identidad.

🎯

Set

Un diccionario sin valores. Pertenencia rápida y unicidad garantizada por construcción, sin posibilidad de duplicados.

🔢

Array

Acceso por índice en tiempo casi constante. Útil en cálculo numérico y rara vez necesario en el estado de una interfaz.

Array: la estructura que se pide mucho y se necesita poco

El Array de Elm ofrece lectura y escritura por índice sin recorrer, sobre una estructura de árbol ancho que aproxima el coste constante. Es la respuesta correcta cuando los datos son una rejilla, una matriz o un búfer numérico que se consulta por posición muchas veces. No lo es cuando la posición solo sirve para identificar un elemento, que es el uso que la mayoría le da al llegar de otros lenguajes.

-- Adecuado: la posicion es parte del significado del dato
tablero : Array Celda

celda : Int -> Array Celda -> Maybe Celda
celda i =
    Array.get i

-- Inadecuado: aqui el indice solo suple a una identidad de verdad
-- usuarios : Array Usuario   -- borrar uno desplaza a todos los demas

El problema de usar el índice como identidad es que el índice no es estable: al eliminar un elemento, todos los posteriores cambian de posición, de modo que cualquier referencia guardada en el modelo queda apuntando a otro dato sin que nada falle visiblemente. Es una fuente clásica de errores silenciosos en interfaces con listas editables, y desaparece por completo en cuanto la identidad se representa con una clave explícita.

Elegir la colección del Model

La pregunta que decide la elección no es cómo son los datos sino qué se hace con ellos la mayor parte del tiempo. Si la operación dominante es mostrarlos todos en orden, la lista gana. Si es actualizar uno concreto en respuesta a una acción del usuario, gana el diccionario. Si es preguntar si algo está marcado, gana el conjunto. Y cuando hacen falta las dos cosas a la vez, la combinación idiomática consiste en separar la identidad del orden.

-- Entidades por identidad, orden aparte, y ninguna duplicacion de datos
type alias Model =
    { usuarios : Dict Int Usuario
    , orden : List Int
    }

visibles : Model -> List Usuario
visibles modelo =
    List.filterMap (\id -> Dict.get id modelo.usuarios) modelo.orden

Este patrón resuelve de golpe los dos problemas: actualizar un usuario toca solo el diccionario y no altera el orden, y reordenar la vista toca solo la lista de identificadores y no duplica ninguna entidad. Es la misma idea que en otros ecosistemas se conoce como estado normalizado, y en Elm no necesita ninguna biblioteca porque las dos piezas ya están en la biblioteca estándar.

💡

Cambiar de colección es un refactor guiado por el compilador

Convertir un campo de List a Dict en un modelo maduro asusta menos de lo que parece, porque el compilador señala uno a uno todos los puntos donde el tipo dejó de encajar y no hay ninguna manera de olvidarse de uno. La estrategia práctica consiste en cambiar el tipo del campo, compilar, y dejarse llevar por la lista de errores hasta que se agote. La mayoría de esos puntos se simplifican en lugar de complicarse, porque el recorrido lineal que había allí desaparece.

⚡

Elegir una colección es declarar cuál es la operación que define tus datos

Detrás de la elección entre estas cuatro estructuras hay una idea que va mucho más allá de la biblioteca estándar de Elm, y es que una estructura de datos no es un contenedor neutral sino una afirmación sobre qué operaciones son importantes. Cuando alguien guarda sus entidades en una lista está afirmando, sépalo o no, que lo esencial de esos datos es su orden y que acceder a uno concreto es excepcional; cuando las guarda en un diccionario está afirmando que lo esencial es que cada una tiene una identidad y que el orden es una cuestión de presentación. Ambas afirmaciones pueden ser correctas, pero solo una lo será para un dominio dado, y el coste de equivocarse no se cobra en microsegundos sino en forma de código. Un modelo que guarda entidades identificables en una lista genera, en cada rama de actualización, un recorrido que compara identificadores y reconstruye la lista entera con el elemento sustituido; ese recorrido no es solo trabajo desperdiciado, es sobre todo ruido que oculta la intención, porque lo que el programador quería decir era cambia el nombre de este usuario y lo que el código dice es recorre todos los usuarios comprobando cuál coincide y construye una lista nueva. La distancia entre esas dos frases es la deuda que se paga por haber elegido mal. Hay un segundo motivo, más sutil, para tomarse en serio la elección: las estructuras difieren en qué invariantes garantizan gratis. Un conjunto no puede contener duplicados, y esa imposibilidad no cuesta nada ni hay que comprobarla nunca; una lista sí puede, y por tanto todo el código que la consuma tiene que decidir qué significa un duplicado o ignorarlo y esperar lo mejor. Un diccionario garantiza que una clave apunta a un solo valor; una lista de pares no garantiza nada. Elegir la estructura correcta es, en este sentido, la misma disciplina que estrechar el modelo con custom types en la tercera lección: en ambos casos se trata de que el tipo del dato prohíba las situaciones que el dominio no admite, en lugar de dejar que las prohíba una comprobación escrita a mano. Y como en aquel caso, la señal de que la elección fue buena es negativa y se reconoce a simple vista: el código que consume la colección deja de contener comprobaciones defensivas, deja de recorrer para encontrar y empieza a leerse como una descripción de lo que la aplicación hace.

⚔️ Elige la estructura por su operación dominante

Toma un modelo con una lista de entidades y cuenta cuántas ramas de la actualización la recorren solo para localizar una.
Convierte esa lista en un diccionario indexado por identificador y compara el tamaño de esas mismas ramas.
Sustituye una lista de elementos marcados por un Set y explica qué comprobación de duplicados deja de ser necesaria.
Implementa el patrón de diccionario de entidades más lista de orden y escribe la función que produce la vista ordenada.
Intenta usar como clave de un diccionario un identificador envuelto en un custom type, lee el error y resuelve el problema.
Modela una rejilla con Array y argumenta por qué la misma estructura sería una mala elección para una lista editable.