Una estructura es completamente persistente si todas las versiones pueden ser accedidas y modificadas.
[1] La persistencia se puede lograr simplemente copiando las estructuras completas, pero esto puede ser muy ineficiente en cuanto a cálculos del CPU y consumo de memoria RAM, debido a que generalmente solo se hacen pequeños cambios.
Lo mejor sería explotar la similitud que existe entre la nueva versión y sus versiones anteriores, y compartir parte de su estructura con ellas, como por ejemplo, utilizar algunos subárboles que no se modificaron para el caso de las estructuras formadas por árboles.
De todas formas, debido a que rápidamente se vuelve no factible determinar cuantas versiones anteriores comparten partes en común con la estructura actual y a que a veces se hace necesario descartar versiones anteriores, es necesario contar con recolector de basura.
Cada nodo debe permitir guardar cualquier cantidad de campos adicionales.
Para el acceso, debemos encontrar la versión correcta en cada nodo mientras recorremos la estructura.
Copia de camino consiste en copiar todos los nodos en el camino desde la raíz del árbol hasta el nodo que vamos actualizar, insertar o borrar.
Estas modificaciones provocan más cambios en cascada, y así sucesivamente, hasta que lleguemos a la raíz.
De lo contrario, se crea una copia del nodo, pero utilizando solo los últimos valores, o sea sobrescribiendo la propiedad o puntero que se encuentra en el campo de modificación, y se hace la modificación directamente en el nuevo nodo, sin utilizar el campo de modificación, o sea, se sobrescribe la propiedad o el puntero directamente y el campo de modificación se queda vacío.
Si el nodo no tiene padre, o sea, es la raíz, y hay que copiarla, se añade en una lista ordenada de raíces.
Cada una de las k copias tiene O(1) costo temporal y espacial, pero disminuye la función potencial en uno, debido a que el nodo que se copia debe estar lleno y vivo, por lo tanto contribuye a la función potencial, pero al copiarlo y cambiar el puntero de su padre dejará de estar vivo, y la copia tiene el campo de modificación vacío así que no está llena, por lo tanto se reemplazó un nodo lleno vivo, por uno que no está lleno).
La lista enlazada es las estructuras más utilizada en los lenguajes de programación funcionales.
Considere las dos listas: Estas deben ser representadas en memoria de la siguiente forma:
Notemos que el árbol original xs persiste y muchos nodos son compartidos entre ambas versiones.