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.