Infinite collections with ES6 generators

Motivation

Infinite and lazy collections are commonplace in many languages, and they are beginning to find their ways to mainstream Javascript too. With the new iterators and generators spec getting widespread adoption, you can now use them in your projects. They have some very specific use cases which may not come up in everyday coding, but are quite useful in certain situations. The specs are quite new, but libraries are starting to pop up to provide the most useful operations.

In this post, you can learn the basics of the specs as well as a particular use case where you'll likely to use the new techniques. Also you'll learn about one available library which provides most of the basic operations to work with these kinds of collections effectively.

Book

Building GraphQL APIs with AWS AppSync

How to design, implement, and deploy GraphQL-based APIs on the AWS cloud

Infinite collections

Arrays

Arrays are inherently finite, as they store all the elements in memory. There is no way to construct them dynamically and they also don't support lazy evaluation. So a construct like this will result in an infinite loop and thus infeasible:

var naturalNums = [];
for(let i = 0;;i++){
	naturalNums.push(i);
}

ES6 Proxies might change this, as they add support to dynamic getters. You might think that a construct like this would result in an array containing all the natural numbers:

var naturalNums = new Proxy({},
	{get: (target, name) => {
		if (!isNaN(name)) {
			return Number(name);
		}else if (name === "length"){
			return Number.POSITIVE_INFINITY;
		}
	}
});

It indeed creates an array-like object that returns all the natural numbers, but unfortunately in practice it's hardly usable. It is missing essential Array functions like splice; it makes them unsupported by libraries like Underscore.js. In theory, you can write utility functions like filter and map, but it's definitely not mainstream.

Iterators

Then iterators came to the rescue. They allow infinite collections and even have a built-in language construct to iterate them: the for-of loop. To construct an iterable, you need to return an iterator for the Symbol.iterator key. The iterator only needs a next() method that returns an object with a done and a value keys. The former indicates whether there are more elements, and the latter contains the actual element. You can create an iterator like this:

var naturalNums = {
	[Symbol.iterator]: (()=>{
		let i = 0;
		return {
			next: () => {
				return {done: false, value: i++};
			}
		}
	})
};

And you can iterate over it using the for-of loop (just don't forget to terminate it, because it's an infinite collection!):

for(let i of naturalNums){
	if(i > 10) break; // Don't forget to terminate!
	console.log(i);
}

Generators

Generators are just syntactic sugar over iterators. Instead of writing all the boilerplate, you can concentrate at the logic. The same iterable can be created using a generator:

var naturalNums = function* (){
	let i = 0;
	while(true){
		yield i++;
	}
}

And you need to call it when you are iterating over it:

for(let i of naturalNums()){
	if(i > 10) break;
	console.log(i);
}

Usage

Why would you need infinite collections? They came handy when you don't know how many elements you'll need in advance. For example, calculating the sum of the first 100 positive numbers is pretty straightforward (this example uses Underscore.js):

const sum = _.chain(_.range(1, 101))
	.reduce((memo, val) => memo + val, 0)
	.value();

But calculating the first 100 primes are a bit harder:

const sum = _.chain(_.range(1, 100000)) // what should stop be?
	.filter(isPrime)
	.first(100)
	.reduce((memo, val) => memo + val, 0)
	.value();

Gentoo library - Generator tools

The widely used libraries, like Underscore.js, do not support iterators. They are based on arrays and array-likes. Fortunately there are already a few projects filling the gap. It's still early days, but they are slowly becoming mainstream. The one I've found quite usable is called Gentoo and it has the basic utility functions you'd need when you are working with collections, like filter, map, and reduce. The original repo seems abandoned, but feel free to use my fork, as it has some additional features like takeWhile and chaining. Just drop in the library and the babel polyfill for the generators and you're good to go.

Browser support

Despite being a relatively new and still little known technology, browser support is quite good. Chrome, Firefox, and Edge all have proper support, only Safari is lagging behind. But with compilers like Babel, you can transpile your code to ES5; just include the polyfill, as that's required in runtime.

NB!

When you are working with infinite collections, always make sure you use an operator that limits the output. It is quite easy to make an infinite loop and break your app.

The infinite way

Using the gentoo library, the previous example can be written in a more effective and robust way:

const sum =
	gentoo.chain(gentoo.range(1, Number.POSITIVE_INFINITY))
		.filter(isPrime)
		.limit(100)
		.reduce((memo, val) => memo + val, 0)
		.value()

This solution does not have any magic numbers that are error-prone, making it a more robust way. It is also effective, as there are no wasted operations.

Closing remarks

Generators are already supported by the major browsers, and you can compile your code with Babel to use them in older ones. You can use them today without any hassle, and while their use cases are quite limited, they will certainly make your code more readable if you use them effectively.