jmvalenciz - Mar 3, 2024

Lazy Arrays en Typescript

TL;DR

Implementación de una forma algo más eficiente de manejar arreglos que descubrí hace algún tiempo en Rust. La implementación realizada aquí no la consideraría usable en producción pero pueden buscar alternativas en http://npmjs.com como lazy.

Análisis

Seguramente en algún momento, has tenido que ejecutar una serie de pasos sobre un arreglo en Javascript y terminaste con algo muy parecido a esto:

var input_array = [0,1,2,3,4,5,6,7,8,9];
var result = input_array.filter(i=>i%2==0).map(i=>i*10); //algo como esto
console.log(result); // OUTOUT: [0,20,40,60,80,90]

Una lista de elementos que deben ser procesados por varias funciones que van a mutar el propio arreglo definiendo una especie de pipeline o línea de producción en donde la salida de el paso actual es la entrada del paso siguiente. Hasta aquí todo está bastante bien. Tomamos un arreglo, lo procesamos por una serie de pasos y obtenemos el resultado que queremos y podemos terminar la característica, ir a casa y ver otro capítulo de nuestra serie favorita de Sci-Fi (que obviamente es Star Trek¹) pero, cómo funciona esto por dentro?

Lo que quiero decir es, que aunque indudablemente funciona, es esta la más óptima de hacer este tipo de procesos? Y es que javascript lo que hace es que cuando uno ejecuta arr.filter().map(), el lenguaje va filtrar todos los elementos del arreglo de golpe, nos va a retornar un arreglo filtrado y luego va a ejecutar el map() con todos los elementos de golpe nuevamente lo que puede no ser la mejor. Para entender mejor este escenario, supongamos una función breakWhen():

Array.prototype.breakWhen((f:T)=>boolean)

que va a dar todos los elementos del arreglo hasta que la condición del método que recibe como argumento sea verdadera así:

var input_array = [0,1,2,3,4,5,6,7,8,9];
var result = input_array.filter(i=>i%2==0).map(i=>i*10).breakWhen(i=>i>45)
console.log(result); // OUTPUT: [0,20,40]

Resulta que en este caso, tanto filter() como map() van a analizar todos los elementos del arreglo pero van a haber 2 elementos que directamente no se debieron haber procesado (el 60 y el 80) y podríamos decir que esto no es un problema porque pudimos haber descartado los elementos que no se debieron haber procesado en el filter() y en este caso es verdad. Pero qué pasaría en el caso de que no sepamos si hay que filtrar los elementos sino hasta después de hacer el map()? como por ejemplo si tenemos que hacer peticiones http y debemos seguir hasta que se cumpla una condición en la respuesta de un api. En ese caso, el breakWhen() solo serviría si los arreglos cumplen con la condición de ser Lazy.

Y bueno, qué quiere decir “Lazy”

Cuando uno explora otros lenguajes de programación, empieza a notar que el hecho de que hagan cosas diferentes no se queda tan solo en la sintaxis (poner u omitir el punto y coma, tener una notación diferente para los arreglos, etc.) sino que también implica que cosas tan básicas como el manejo de algunos elementos primitivos tienen implicaciones que mejoran el rendimiento en algunos casos como por ejemplo Rust² que maneja un concepto llamado Lazy que, según la documentación oficial:

In Rust, iterators are lazy, meaning they have no effect until you call methods that consume the iterator to use it up

The Rust Programming Language - Iterators

Esto básicamente quiere decir que los elementos de un iterador se obtienen bajo demanda o, en términos de un pipeline, se va a procesar únicamente el proceso cuando yo lo solicite, hasta que obtenga el siguiente elemento al final de la “línea de producción” lo que suena curiosamente similar a los iteradores y generadores de javascript. Y esto no es casualidad porque al final, un generador me va dar una función next() que me permite obtener el siguiente elemento:

*function mi_generador(){ // el * transforma la función en un generador
	for(let i=0;i<50;i++){
		yield i*2; // yield nos da el siguiente elemento
	}
}

const i = mi_generador();
console.log(i.next()) // OUTPUT: { value: 0, done: false }
console.log(i.next()) // OUTPUT: { value: 2, done: false }
console.log(i.next()) // OUTPUT: { value: 4, done: false }
console.log(i.next()) // OUTPUT: { value: 6, done: false }
...
console.log(i.next()) // OUTPUT: { value: 96, done: false }
console.log(i.next()) // OUTPUT: { value: 98, done: false }
console.log(i.next()) // OUTPUT: { value: undefined, done: true }

Aquí puede que digas: solucionado, no es así? si ya tenemos generadores, no debería ser un problema el caso planteado anteriormente con las peticiones al un api. Y… no realmente porque, aunque los generadores si son lo que necesitamos, los arreglos en Javascript no están implementados con esta tecnología y justo un ejemplo esa implementación es lo que quiero mostrar en este post 👍.

Implementación de Lazy Arrays

Antes de empezar, hay un par de cosas que es importante entender para poder seguir:

Javascript Generators
Builder Pattern en Javascript o la definición original de Gof para los más valientes
Typescript Generics
Un repaso a algunos métodos de los arreglos de Javascript como por si es necesario refrescar conceptos

Para este ejemplo, vamos a implementar únicamente los siguientes métodos para mantenerlo sencillo (algunos son parte de Rust entonces pondré el enlace a su documentación pero confíen en mí, es fácil de leer 🌚):

map()
filter()
forEach()
breakWhen() (este es del ejemplo propuesto más arriba)
splice()
take() (Rust) con la capacidad de poder especificar en donde se inicia
into_iter() (Rust) que aquí lo vamos a llamar from()
into_generator() Parte de la implementación que nos va a dar un iterable que podemos usar en un for loop

Ahora si. Lo primero, es construir el esqueleto del proyecto y, como queremos que se pueda usar con arreglos de cualquier tipo, vamos a usar Generics de Typescript:

class LazyIter<T> {
    #iterator: Generator<T>;

    private constructor(iterator: Generator<T>){
        this.#iterator = iterator;
    }

    static from<U>(input: Array<U>|Generator<U>){
        if(Array.isArray(input)){
            return new LazyIter(this.#to_generator(input));
        }
        return new LazyIter(input);
    }

    static *#to_generator<U>(arr:Array<U>){
        for(const i of arr){
            yield i;
        }
    }

    filter(f: (i:T)=>boolean): LazyIter<T>{
        return new LazyIter(...);
    }

    map(f: (i:T)=>any): LazyIter<T>{
        return new LazyIter(...);
    }

    take(start:number, n:number):LazyIter<T>{
        return new LazyIter(...);
    }

    breakWhen(f:(i:T)=>boolean): LazyIter<T>{
        return new LazyIter(...);
    }

    forEach(f: (i:T)=>void): LazyIter<T>{
        return new LazyIter(...);
    }

    splice(i: number, deleteCount: number): LazyIter<T>{
        return new LazyIter(...);
    }

    into_generator(): Generator<T>{
        return this.#iterator;
    }
}

Ok, ya hay varias cosas que analizar. Lo primero es aclarar que la estructura de la clase está diseñada para que cada etapa de nuestro “pipeline” sea una instancia de LazyIter de modo que si yo tengo el siguiente código:

const arr = [0,1,2,3,4,5,6,7,8,9];
const iter = LazyIter.from(arr).filter(...).map(...)

internamente sería lo siguiente:

En donde los círculos representan las instancias de LazyIter y la variable iter tiene el valor del último elemento del pipeline por lo que una vez que ejecutemos into_generator() y empecemos a iterar, iter va a solicitarle un elemento a map(), este a filter() y este al arreglo.

1. Constructor privado

Todo nuestro sistema se basa en manejar generadores, pero el desarrollador por lo general nos va a pasar es un arreglo. Debido a esto, vamos a ocultar el constructor y vamos a crear la función from() que se va a encargar de llamar al constructor en el formato que lo necesitamos

2. *#to_generator()

La clase va a estar habilitada para recibir elementos de tipo arreglo o de tipo generador por lo que, si es un elemento de tipo generador, lo vamos a pasar tal y como llega al constructor. Pero si el elemento es de tipo arreglo, lo vamos a transformar en un generador antes de pasarlo al constructor usando este método estático

3. Por qué siempre retornamos una instancia de LazyIter?

Como comenté hace un momento, la clase va a manejar cada etapa como una instancia de LazyIter. Esto nos permite que nosotros podamos encadenar los métodos que queremos llamar siempre y cuando estén definidos en la clase:

const iter = LazyIter.from([1,2,3,4,5]).map(...).filter(...).breakWhen(...).splice(...)take(...)

4. into_generator()

Al final de la definición de todos los pasos del pipeline, necesitamos retornar un elemento que sea usable por javascript que en este caso sería un elemento de tipo Generator<T> en donde T es el tipo de datos de nuestro arreglo de modo que into_generator() se encarga de hacer esta transformación:

const iter = LazyIter.from([1,2,3,4,5]).map(...).filter(...).breakWhen(...).splice(...)take(...);
const g = iter.into_generator();
for(let i in g){
	console.log(i);
}

Implementación de los métodos

Ahora lo que sigue es configurar los métodos como filter(), map(), etc. Debido a que Javascript no deja usar funciones flecha como Generadores, decidí ir por lo que me parecía la segunda mejor opción que es crear métodos privados en la clase de modo que la implementación de filter() quedaría algo así:

class LazyIter<T>{
...
	filter(f: (i:T)=>boolean): LazyIter<T>{
		return new LazyIter(this.#filter(f));
	}
	*#filter(f: (i:T)=>boolean){
		for(const i of this.#iterator){
			if(f(i)){
				yield i
			}
		}
	}
...
}

Y extrapolando el resultado al resto de los métodos, la implementación completa quedaría así:

class LazyIter<T> {
	#iterator: Generator<T, void>;

	private constructor(iterator: Generator<T>){
		this.#iterator = iterator;
	}

	static from<U>(input: Array<U>|Generator<U>){
		if(Array.isArray(input)){
			return new LazyIter(this.#to_generator(input));
		}
		return new LazyIter(input);
	}

	static *#to_generator<U>(arr:Array<U>){
		for(const i of arr){
			yield i;
		}
	}
	
	filter(f: (i:T)=>boolean): LazyIter<T>{
		return new LazyIter(this.#filter(f));
	}

	*#filter(f: (i:T)=>boolean){
		for(const i of this.#iterator){
			if(f(i)){
				yield i
			}
		}
	}

	map(f: (i:T)=>any): LazyIter<T>{
		return new LazyIter(this.#map(f));
	}

	*#map(f: (i:T)=>any){
		for(const i of this.#iterator){
			yield f(i);
		}
	}

	take(start:number, n:number):LazyIter<T>{
		return new LazyIter(this.#take(start, n));
	}

	*#take(start:number, n:number){
		let c = 0;
		for(let i of this.#iterator){
			if(c<start){
				c++;
				continue;
			}
			if(c>start+n){
				break;
			}
			c++;
			yield i;
		}
	}

	breakWhen(f:(i:T)=>boolean): LazyIter<T>{
		return new LazyIter(this.#breakWhen(f));
	}

	*#breakWhen(f:(i:T)=>boolean){
		for(const i of this.#iterator){
			if(f(i)){
				break;
			}
			yield i;
		}
	}

	forEach(f: (i:T)=>void): LazyIter<T>{
		return new LazyIter(this.#forEach(f));
	}

	*#forEach(f: (i:T)=>void){
		for(const i of this.#iterator){
			f(i);
			yield i;
		}
	}

	splice(i: number, deleteCount: number): LazyIter<T>{
		return new LazyIter(this.#splice(i, deleteCount));
	}

	*#splice(i: number, deleteCount: number){
		let toDelete = deleteCount;
		let curr = 0;
		for(const n of this.#iterator){
			if(curr++>=i && toDelete > 0){
				toDelete--;
				continue;
			}
			yield n;
		}
	}

	into_generator(): Generator<T>{
		return this.#iterator;
	}
}

Y por último, podemos probar el código con algunos casos de uso:

function *g(){
	yield 1;
	yield 2;
	yield 3;
	yield 4;
}

const l = LazyIter.from([1,2,3,4,5,6,7,8,9,10]);
const m = LazyIter.from(g());

const iter = l.filter(i=>i%2==0).map(i=>i*10).into_generator();
const iter2 = m.filter(i=>i%2==0).map(i=>i*10).into_generator();

console.log("Arreglo");
for(const i of iter){
	console.log(i);
}
console.log("Generador");
for(const i of iter2){
	console.log(i);
}

# OUTPUT:
Arreglo
20
40
Generador
20
40

Pensamientos finales

IMPORTANTE: Como mencioné en el TL;DR, este código es únicamente un ejemplo y NO está listo para producción. Le faltan pruebas unitarias, limpieza, algo de orden y configurarlo como un paquete de node. Si quieren un paquete que seguramente esté mucho más probado que este código, pueden revisar lazy.

También considero que la implementación que realicé, se puede mejorar con respecto al hecho de tener que separar la implementación de los generadores y los handlers (por ejemplo: filter() y *#filter()) por lo que si encuentro algo que considere como una implementación más limpia, haré una nueva entrada con los ajustes pertinentes.

Disclaimer: es sólo una broma, Star Wars también es bueno y no hay por que pelear como los que dicen que Vim/Emacs es el mejor editor de código porque todos sabemos que al final ambos son muy buenos… y también sabemos que NeoVim es el mejor. ↩
Perdón a mis amigos que ya deben estar cansados de Rust de tanto que lo mensiono ↩