Estructuras persistentes e inmutables
Una estructura persistente no se modifica: cada cambio devuelve una versión nueva y las anteriores siguen enteras. Suena carísimo y no lo es, porque las versiones comparten casi todo. Es la idea detrás del deshacer, de git y de la mitad del ecosistema funcional.
Para este tema conviene tener claro:Árboles binarios y recorridosListas enlazadas
La intuición dice que guardar cada versión de una estructura cuesta copiarla entera: mil versiones de un árbol de un millón de nodos serían mil millones de nodos.
Es falso, y por un motivo simple: si nada cambia, nada hay que copiar. Al modificar un árbol sólo cambia el camino de la raíz hasta el nodo tocado; todo el resto puede ser exactamente el mismo, compartido entre las dos versiones. Guardar una versión nueva cuesta nodos, no .
Qué quiere decir persistente
| Efímera (la habitual) | Persistente parcial | Persistente total | |
|---|---|---|---|
| Qué hace una modificación | Cambia la estructura | Devuelve una versión nueva | Devuelve una versión nueva |
| Versiones anteriores | Se pierden | Se pueden leer | Se pueden leer y modificar |
| Quién la usa | Casi todo el código imperativo | Historiales, auditoría | Lenguajes funcionales, deshacer y rehacer |
Copia de camino, paso a paso
Versión 1 del árbol. Nadie la va a modificar: sólo se le van a agregar versiones al lado.
Tres nodos nuevos para una versión entera. En un árbol equilibrado de un millón de elementos serían unos veinte: la altura del árbol.
Antes de seguir, predecí
El caso más barato: la lista
Una lista enlazada inmutable es persistente casi sin esfuerzo: agregar adelante cuesta un solo nodo, y la lista vieja sigue siendo una lista válida.
type ImmutableList<T> = { readonly head: T; readonly tail: ImmutableList<T> } | null;
const prepend = <T,>(list: ImmutableList<T>, value: T): ImmutableList<T> => ({
head: value,
tail: list,
});
const original = prepend(prepend(null, 2), 1);
const derived = prepend(original, 0);derived tiene tres elementos y original sigue teniendo dos: no se copió nada, el nodo nuevo
apunta a la lista vieja. Por eso las pilas inmutables son gratis, y por eso agregar al final de
una lista inmutable no lo es: habría que copiar todo el camino hasta la punta.
Cómo hacen los lenguajes funcionales
Un arreglo inmutable con acceso por índice no puede ser una lista enlazada. La solución habitual es un árbol de ramificación ancha —típicamente 32 hijos por nodo— donde el índice se lee en grupos de cinco bits para bajar por el árbol.
| Operación | Arreglo mutable | Copiar el arreglo entero | Árbol de 32 ramas |
|---|---|---|---|
| Leer por índice | O(1) | O(1) | O(log₃₂ n): a lo sumo unos siete saltos |
| Modificar una posición | O(1) | O(n) | O(log₃₂ n): se copia un camino de siete nodos |
| Agregar al final | O(1) amortizado | O(n) | O(log₃₂ n) amortizado |
| Versión anterior | Se perdió | Se conserva, duplicando memoria | Se conserva, compartiendo casi todo |
Lo mismo vale para los diccionarios inmutables, que se implementan como tries de hash con la misma ramificación: el hash de la clave se lee en grupos de bits y cada grupo elige una rama.
Dónde aparece
| Uso | Qué aporta la persistencia |
|---|---|
| Deshacer y rehacer | Cada estado anterior es una versión que sigue viva, sin snapshots caros |
| Detectar cambios en una interfaz | Comparar por identidad alcanza: si el objeto es el mismo, nada cambió |
| Concurrencia | Varios hilos leen la misma estructura sin candados: nadie escribe |
| Auditoría e historial | El estado en cualquier momento del pasado es consultable |
| git | Cada commit es un árbol nuevo que comparte todo lo que no cambió |
| Copiar al escribir en sistemas de archivos | Snapshots instantáneos: sólo se copian los bloques modificados |
Más a fondo · nivel seniorPersistencia total y el truco de los nodos gordos
La copia de camino da persistencia con un costo de por versión. Hay una técnica —atribuida a Driscoll, Sarnak, Sleator y Tarjan— que la baja a amortizado: en vez de copiar el nodo, se le agrega espacio para unas pocas modificaciones extra, cada una con el número de versión en la que ocurrió. Leer la versión significa tomar, en cada nodo, la última modificación con número menor o igual a . Cuando el espacio extra se llena, ahí sí se parte el nodo y se propaga hacia arriba.
Es más complejo de implementar y rara vez aparece en código de producción, pero explica por qué la persistencia es, en teoría, casi gratis: el logaritmo de la copia de camino no es un límite inevitable.
Cierre
Autoevaluación
¿Lo entendiste?
Práctica