Estructuras de datos inmutables

¿Estás seguro de que modificar esa variable no le hará daño al código? ¿No? Bueno, entonces aprendamos de inmutabilidad

Antes de que empecemos te recomiendo que si entiendes inglés vayas y veas esta charla de Anjana Vakil en JSConf EU en la cual está fuertemente inspirada esta lectura.

Si sabemos que algo es mutable cuando puede cambiar podemos deducir es inmutable cuando no puede cambiar.

Ahora bien, para entender de que nos sirve la inmutabilidad veamos el siguiente ejemplo:

Imaginemos que estamos trabajando en equipo y tenemos un set de datos como este:

Pero resulta que queremos cambiar la vaca por un pez, así que hacemos algo así

Sin embargo, El trabajo de nuestro compañero dependía de que la vaca estuviese ahí ¿Entonces que hacemos? Trabajar con datos inmutables.

Ya que nuestros datos son inmutables si queremos realizar cambios lo más sencillo sería hacer una copia modificada. Algo así:

Por la cantidad de recursos que consume y dificultad para manejar múltiples copias, esta solución es lenta y poco escalable. Aquí entran las estructuras de datos persistentes

Las estructuras de datos persistentes son esencialmente estructuras de datos inmutables que pueden volver en el tiempo. Para entenderlas tenemos que pasar a verlas en forma de árbol. Algo así:

Aquí dividimos el set de datos en pares y los conectamos con nodos los cuales se conectan entre sí hasta llegar a un nodo raíz que identificará nuestro set de datos

Ahora, para realizar cambios a nuestros datos, enlazamos los nodos que no cambiaron en nuestro set de datos a un nuevo nodo raíz que identificará al nuevo set de datos. Algo así:

Esta técnica se llama Path Copying y nos permite que el modificar nuestro set de datos inmutable ocupe un menor espacio y sea mucho más rápido que copiarlo todo por cada cambio que realizamos. Con esta técnica también podremos acceder a nuestros datos originales en cualquier momento.

Ahora, para acceder a nuestros datos hagamos como que cada nodo es un bit y cada valor en ese bit representa un camino para llegar a nuestros datos. Algo como esto:

Entonces si quisiéramos llegar a nuestro panda en vez de escribir:

Data[6]

Tendremos que convertir nuestro 6 a binario y acceder de la siguiente forma:

Data[0b110] 

(“0b” es solo un prefijo utilizado para indicar que es un número binario en vez de un número en base 10)

Pero generalmente estos árboles no contienen nodos con solo dos ramas si no de 32 ramas por nivel, representando así 5 bits por nivel. Entonces si tuviéramos un número más grande como:

22693

Que para acceder al mismo con un número binario sería algo así:

Data[0b101100010100101]

Con una estructura de 32 ramas sería algo así:

Data10110--> 00101--> 00101

Así descendemos 3 niveles en lugar de 15.

Hay que tener en cuenta también que este es solo un ejemplo de estructuras de datos inmutables, pero sirve para tener una vista previa de como trabajan las mismas.

Ahora, si quieres aplicar esto en tus proyectos hay librerías de Javascript como Mori o Immutable que nos permiten trabajar con inmutabilidad en nuestros datos de manera muy sencilla.