Un diccionario persistente en 4 líneas de javascript

A raíz de la excelente serie de post que está escribiendo Modesto San Juan sobre la programación orientada a objetos, comentábamos hace poco en twitter que a veces la programación funcional y la programación orientada a objetos ofrecen dos enfoques distintos para alcanzar lo mismo, y cómo ambos paradigmas cuentas con estructuras “idomáticas” para implementar conceptos del otro.

Todos los que hemos tocado javascript en algún momento hemos vivido esa sensación de estar simulando conceptos de programación orientada a objetos con funciones (con closures concretamente), pero lo cierto es que puede parecer algo anecdótico o impuesto por las “limitaciones” del lenguaje. 

Sin embargo, hay veces que modelar “objetos” o, siendo más correcto, estructuras de datos, con construcciones puramente funcionales, puede llegar a ser una solución mucho más sencilla.
A los que conozcáis el libro Structure and Interpretation of Computer Programs el ejemplo que vamos a ver en este post os resultará simplista, pero a los que no lo hayáis leido tal vez os resulte curioso y os anime a leer el libro (merece la pena, en serio).

Un diccionario inmutable y persistente

Vamos a implementar una estructura de datos que represente un diccionario, o un array asociativo, como se le conoce en otros ámbitos, que almacene un conjunto de pares clave/valor. Las operaciones básicas serán: crear un diccionario vacío, asociar una clave a un valor, eliminar la asociación entre una clave y un valor, y, por supuesto, obtener el valor asociado a una clave.

Hasta aquí, no parece un problema muy complicado y, de hecho, casi todos los lenguajes de programación que conozco incluyen una estructura de datos similar en su librería estándar. Aun sin usarla, crear nuestra propia implementación sería bastante sencillo a partir de una lista de pares.

Para hacerlo más interesante, vamos a intentar que nuestro diccionario sea inmutable y persistente. Es decir, cuando añadamos o eliminemos entradas del diccionario, queremos que no se modifique el diccionario original, sino que se cree un diccionario totalmente nuevo con los cambios que sea necesario. Y claro, queremos que estas operaciones de adición y eliminación sean eficientes. A ser posible, que tengan una complejidad algorítmica constante (O(1)). Además, hay que vigilar el consumo de memoria y evitar que al añadir un valor al diccionario acabemos teniendo dos copias en memoria de todo el diccionario original.

Resumiendo, si aprovechamos que todo el mundo es capaz de leer javascript y usamos ese lenguaje para especificar el problema, queremos un api así:

// Devuelve un diccionario vacío
function emptyDict() { ... }

// Obtiene el valor asociado a `key` en `dict`,
// o `null` si `key` no está en el diccionario
function get(dict, key) { ... }


// Crea un nuevo diccionario igual que `dict`, 
// pero en el que `key` está asociado a `value`.
// El diccionario original *no* debe ser modificado.
function set(dict, key, value) { ... }

// Crea un nuevo diccionario igual que `dict`, 
// pero que ya no contiene `key`.
// El diccionario original *no* debe ser modificado.
function remove(dict, key) { ... }

Con este api, deberíamos ser capaces de pasar estos tests:

let d = emptyDict();

assertEquals(null, get(d, 'lucas'), 'd no contiene nada');

let d1 = set(d, 'lucas', 10);

assertEquals(10, get(d1, 'lucas'), 'd1 contiene lucas');
assertEquals(null, get(d, 'lucas'), 'pero d sigue vacío');

let d2 = set(d1, 'marcos', 20);

assertEquals(10, get(d2, 'lucas'), 'd2 contiene lucas');
assertEquals(20, get(d2, 'marcos'), 'd2 contiene marcos');
assertEquals(null, get(d1, 'marcos'), 'pero d1 *no* contiene marcos');

let d3 = remove(d2, 'lucas');

assertEquals(null, get(d3, 'lucas'), 'd3 ya *no* contiene lucas');
assertEquals(20, get(d3, 'marcos'), 'd3 contiene marcos');
assertEquals(10, get(d2, 'lucas'), 'd2 sigue conteniendo lucas');
assertEquals(20, get(d2, 'marcos'), 'd2 sigue conteniendo marcos');

Si queréis probar a implementar esto con un enfoque más “OOP”, veréis que es relativamente fácil, siempre y cuando ignores las restricciones de eficiencia a la hora de insertar y eliminar, y no te preocupes por el consumo de memoria. En cuanto quieres introducir la inmutabilidad necesitas empezar a copiar objetos o arrays, y la cosa se complica un poco.

Una solución natural basada en funciones

Vamos a intentar resolver el problema utilizando sólo funciones, sin recurrir a objetos de javascript (que no dejan de ser diccionarios en si mismos), ni arrays. Aunque pueda parecer extraño, la solución es bastante natural (y curiosa si no has visto muchos ejemplos de este tipo).

Empezamos por crear un diccionario vacío.

¿Cuál es nuestra definición de diccionario vacío? Un diccionario que no contiene claves, es decir, un diccionario en el cual, para cualquier clave que utilicemos se cumple que get(dict, key) === null.

Puesto que la definición de diccionario vacío depende de la definición de get, implementemos ambas a la vez:

function emptyDict() {
  return function(k) {
    return null;
  };
}

function get(dict, key) {
  return dict(key);
}

Vale, a primera vista es un poco raro, pero vamos a analizarlo despacio.

Implementaremos un diccionario como una función, aunque eso es totalmente transparente para el usuario del diccionario, que sólo accederá a él a través del api definida en el punto anterior.

Para extraer valores del diccionario, invocaremos la función que representa al diccionario con la clave cuyo valor queremos obtener. Eso es exactamente lo que tenemos en la función get. Por tanto, un diccionario vacío será una función que, independientemente del valor que le pasemos como parámetro, siempre devolverá null que, recordemos, es el comportamiento que hemos definido para el caso de acceder a claves no presentes en el diccionario. Otra opción sería lanzar un error (y la implementación sería análoga cambiando el null por un throw "Invalid key" o algo similar).

¿Cómo añadimos valores al diccionario?

Puesto que estamos implementando el diccionario como una función, necesitaremos crear una función que, cuando reciba la clave añadida, devuelva el valor asociado. Para el resto de valores, deberá comportarse exactamente igual que el diccionario original:

function set(dict, key, value) {
	return function(k) {
		return k === key ? value : get(dict, k);
	};
}

Sencillo, ¿no? Nuestra nueva función devuelve el valor asociado a key al ser invocada con ese parámetro, y delega el resto de claves a lo que ya hubiera antes.

Sólo nos queda eliminar valores del diccionario, y a estas alturas seguro que te puedes imaginar cómo hacerlo:

function remove(dict, key) {
	return function(k) {
		return k == key ? null : get(dict, k);
	};
}

Como era de esperar, creamos una nueva función en la cual, cuando se intenta acceder al valor eliminado, devuelve null, y para el resto de valores, delega el resultado al diccionario original.

Si juntamos todo el código y lo ponemos en bonito (con las arrow functions de ES2015), nos quedan las siguientes 4 líneas:

const emptyDict = () => () => null;
const get = (dict, key) => dict(key);
const set = (dict, key, value) => k => key === k ? value : dict(k);
const remove = (dict, key, value) => k => key === k ? null : dict(k);

Sin llegar al Code Golf, hay que reconocer que queda una implementación bastante simple (lo de sencilla lo dejo ya a vuestro criterio).

Cumple con todos los requisitos indicados al principio: inmutabilidad, persistencia, coste constante para inserción y eliminación, y consumo mínimo de memoria. No he implementado la solución a partir de objetos o arrays, pero estoy casi seguro de que requiere más código.

Por si alguien se plantea si esto es usable, hay que tener en cuenta dos cosas: el coste de acceso para obtener un elemento es un triste O(n) y, dependiendo del tamaño del diccionario, te arriesgas a obtener un stack overflow si el jitter que ejecuta el código no es capaz de optimizar la recursión final (desconozco si V8 lo hace, por comparar, creo que la JVM no es capaz y que .NET sólo lo hace en 64 bits).

Resumen

Es divertido jugar con distintos enfoques a la hora de resolver un problema. Incluso problemas que, a priori, nos pueden parecer muy indicados para aplicar un enfoque concreto, una vez analizados nos pueden acabar sorprendiendo.

Si nunca te habías parado a pensarlo y te hubieran dicho que una forma muy sencilla de implementar un diccionario persistente es sólo con funciones, seguramente te hubiera extrañado, pero la realidad es que la solución es bastante natural. De hecho, utilizar un enfoque OOP clásico para este problema es complicado (sobre todo la parte de evitar duplicar el consumo de memoria con cada inserción/eliminación).

En el mundo real las estructuras de datos persistentes se implementan con técnicas más sofisticadas que permiten asegurar un rendimiento mejor, pero esto no deja de ser un poco de pornografía interesante para pasar el rato.


11 comentarios en “Un diccionario persistente en 4 líneas de javascript

  1. Una solución muy imaginativa. Como anécdota: lo único que me ha chocado es colocar el diccionario (dict) como primer parámetro (get(dict, key)) en lugar del último. Al comenzar el artículo pensaba que la implementación se iba a orientar hacia el “currying”.

  2. No había pensado mucho en el orden de los parámetros, pero me salía “natural” colocar el diccionario al principio. Quizá sea porque los lenguajes que conozco con este tipo de APIs suelen colocarlo ahí.

  3. Micael Gallego dijo:

    Una implementación muy curiosa. Sobre todo para los que no nos movemos muy bien en el paradigma funcional.

    Respecto al consumo mínimo de memoria, si no he entendido mal tu solución, no se cumple, no? Es decir, todos los valores que has insertado acabarán estando para siempre asociados en alguna de las versiones de la función “get” que has ido creando en las inserciones, no? Aunque esas funciones no sean nunca más referenciando “desde afuera”…

    Posiblemente esté equivocado y seguro que no me estoy dando cuenta de algo… Pero yo pregunto para salir de dudas ;)

  4. En lo del consumo de memoria es posible que se me haya pasado algo o que no lo haya explicado del todo bien.

    Me refería a evitar la implementación naïf que implica copiar entera la estructura de datos cada vez que hay un cambio, y que es sumamente ineficiente mientras mantienes referencias a varias versiones del diccionario (algo habitual cuando lo estás construyendo).

    Por ejemplo, si implementas el diccionario como una lista de pares y, cada vez que añades o eliminas copias la lista entera con el nuevo par (o sin el par que has quitado), el consumo de memoria global (contando la versión antigua y la versión nueva del diccionario) se duplica, pasando de N a 2N+1 (o 2N-1 si has eliminado).

    Con la implementación basada en funciones, en cada operación el consumo global sólo aumenta en 1 (siempre pasa de N a N+1). Eso sí, es verdad que cada cambio (ya sea adición o eliminación) implica hacer crecer el consumo global de memoria.

  5. Micael Gallego dijo:

    Ahh, entiendo. Es cierto que la copia es costosa y no se “aprovecha” el espacio cuando varios clientes comparten versiones del diccionario.

    La cosa de que la memoria crezca en cada eliminación es lo que más miedo da… porque al final acumulas sin posibilidad de liberación. Pero como ejercicio teórico es un ejemplo muy simple ;)

  6. No hacen falta varios clientes.

    Si tienes un sólo cliente que añade 100.000 entradas al diccionario durante su inicialización, el coste en memoria antes de salir del método de inicialización (mientras están vivas las 100.000 versiones del diccionario) sería de 1+2+…+100.000 = (100.000*100.000+1)/2 = mucho (del orden de 10^10 * el coste de la entrada).

    Y eso además con un coste cuadrático para hacer la inserción de los N elementos.

    Como siempre, la solución buena depende mucho de lo que necesites conseguir. Hay enfoques “híbridos”, con estructuras de datos mutables acotadas en el tiempo para optimizar el rendimiento, pero que una vez que están construidas por completo se “vuelven” inmutables.

  7. @Juanma En mi caso lo natural ha pasado a ser que el objeto sobre el que actúa la función esté siempre al final para aprovechar el “currying”. Ramda se ha convertido en mi librería de referencia para gran parte de las manipulaciones sobre diferentes objetos en JavaScript y se suele proceder de este modo. ¿No te llama su sintaxis tan funcional?

  8. @Bernal, me gusta ramda, pero la verdad es que luego en javascript utilizar un enfoque tan funcional resulta un poco cansado por todo el ruido que mete la sintaxis. Me pasa igual con librerías como immutable.js: la idea me gusta, pero el lenguaje no es el más cómodo para ello.

  9. Un saludo desde Colombia. Esa capacidad de los cierres léxicos demuestra la versatilidad para construir estructuras de datos de cualquier índole desde las funciones.
    Si en vez de un “value”, lo que se guardara fuera una función, es posible, con algunas modificaciones, jugar a simular herencia en OOP.
    De otra parte, la forma en que expones conceptos es asombrosa e impresiona como un post tan sencillo logra dar luces sobre las ideas.
    Usted debería sumergirse en Haskell para enseñarnos a todos. Clojure es bueno, pero no tiene todo el respaldo de años de investigación en “tipos” para lograr seguridad.

  10. Ha perdido un poco de popularidad el paradigma OOP y ha tomado fuerza el Funcional. Ahora muchos que se entrenaron en OOP durante años, están aprendiendo y encontrando beneficios en el paradigma Funcional. Que opina usted de lo siguiente inquietud:
    Para tener opiniones verdaderamente robustas, lo mejor es que un des arrollador aprenda y haga un programa no tan trivial en cada uno de los paradigmas : Orientado a objetos, Funcional y Lógico ????
    No sea que por alguna razón, el paradigma lógico sea mas requerido en el futuro y muchos “profesionales” del software apenas si conoceran de el y solo sepan de OOP y del funcional.
    Es demasiado utópico pedir que los desarrolladores se formen con una visión universal de las formas de concebir el software ?? Es tan difícil lograrlo ?? No se, son temas interesantes pero mi conocimiento no me da para proponer una respuesta que pueda defender con argumentos

  11. Hola Edwin,

    Lo que planteas es muy interesante y, en mi opinión, acertado.

    No creo que se pueda decir que un paradigma es inherentemente mejor que todos los demás (aunque hay gente cuya opinión respeto mucho que sí lo piensa). Lo que sí creo que es fundamental es conocer distintos paradigmas y enfoques para poder mezclarlos e intentar obtener lo mejor de cada uno.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *

*

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>