Lazy Sequences with ECMAScript 6 Generators

Generators are an ES6 feature that started receiving a lot of attention a few years ago because of their potential to ease some of the pain associated with writing asynchronous code. However, with the emergent async/await proposal (mere syntax sugar around generators and promises), some of the shine has worn off, and generators aren’t getting the same amount of attention they used to.

This is a shame, because even if you disregard their uses in asynchronous code, generators are still pretty cool in their own right. I’m going to explore some of the ways you can use them to implement lazy sequences.

Generators are functions that can be started and stopped, like a mechanical generator. You can feed values into them (like gasoline) and get values back out (like electricity). They can stop permanently if you want them to, or they can run forever and continue to give you new values every time you ask for one. With generators, then, it’s possible to create lazy objects that represent infinite sequences.

Implementing a Generator Without Using a Generator

It’s possible to build an object like this without any special language construct, so let’s build that first and then compare it to a generator. We’ll keep it simple and build something that will return the next multiple of three.

If we had such an object, using it might look like this:


multiplesOf3.next(); //Should be 0
multiplesOf3.next(); //Should be 3
multiplesOf3.next(); //Should be 6

From this code, it’s clear that multiplesOf3 is an object with a next method, so let’s start with that:


const multiplesOf3 = {
    next: () => {
        return "something?";
    }
};

We need it to return the next multiple of three, so it’s going to have to keep some kind of internal state. Attaching a property to the object is no good because it will be directly accessible. We want something private.

Let’s wrap the next function in an anonymous function call. Then we can store some state in its closure:


const multiplesOf3 = {
    next: (() => {
        let state = "state goes here"
        return () => {
            return "something"
        }
    })()
}

This is starting to get kind of ugly now. We’re almost there, though. The body of the function that next returns is going to have to iterate until it finds a multiple of three, and then return it. The current value is stored in state.


const multiplesOf3 = {
    next: (() => {
        let state = -1;
        return () => {
            while (++state % 3);
            return state; 
        }
    })()
};

Now we have something that will work. Let’s look at the generator version:


const multiplesOf3 = function* () {
    let state = -1;
    while (true) {
        while (++state % 3);               
        yield state;
    }
};

let generator = multiplesOf3();
generator.next(); // { value: 0, done: false }
generator.next(); // { value: 3, done: false }

It’s a little more concise, and we don’t have to do any tricks with closures to get a state that will persist between function calls. Generators are declared with function*, and you get an instance by calling that function. Once you have an instance, you can get the next value by calling .next(). You aren’t returned the next value directly, but via an object with value and done properties.

When you call next the first time, the body of the generator starts executing from the top until it encounters the yield keyword. This keyword is like a pause button that stops execution and returns a value back to the caller. When you call next again, execution resumes at the spot of the yield and continues until it encounters another yield.

Using Multiple Generators

Composing generators is as easy as composing functions. Let’s move up a level of abstraction from the previous example. The list of multiples of three is a filtered list of all the integers. With generators, we can build an object that represents the list of all the integers and combine it with an arbitrary filter function to get an object that represents all the multiples of three.


//Filter function
const multipleOf = (factor) => (n) => n % factor === 0;

//Generator for natural numbers
const generateIntegers = function* () {
    let state = 0;
    while (true) {
        yield state++
    }
};

const filterGenerator = function* (generator, filter) {
    while(true) {
        var next = generator.next();
        if (filter(next.value)) {
            yield next.value;
        };
    };
};

let multiplesOf3 = generatorFilter(generateIntegers(), multipleOf(3));
multiplesOf3.next() // { value: 0, done: false }

In this example, filterGenerator takes another generator and a filter, then returns elements of the passed-in generator that meet the filter criteria.

Chaining

Let’s extend the example a little bit so we can chain calls to our filter function. We’re going to follow a familiar convention and make a function to wrap our generator. The object it returns will have a filter function, and I’m also adding a map function.


const wrap = function (generator) {
    const generatorFilter = function* (generator, filter) { 
        while(true) {
            var next = generator.next();
            if (filter(next.value)) {
                yield next.value;
            };
        };
    };

    const generatorMap = function* (generator, map) {
        while(true) {
            yield map(generator.next().value);
        }
    }

    let modifiedGenerator = generator;
    let wrapped = {
        filter: (filter) => {
            modifiedGenerator = generatorFilter(modifiedGenerator, filter);
            return wrapped;
        },
        map: (map) => {
            modifiedGenerator = generatorMap(modifiedGenerator, map)
            return wrapped;
        },
        next: () => {
            return modifiedGenerator.next(...arguments);
        }
    }

    return wrapped
}

//Usage
const perfectNthPower = (nth) => (n) => Math.pow(n, 1/nth) % 1 === 0
const timesThree = (n) => n * 3;
const multipleOf = (factor) => (n) => n % factor === 0;

//'numbers' is going to be perfect squares that are multiples of 5 multiplied by 3
let numbers = wrap(generateIntegers()).filter(multipleOf(5)).filter(perfectNthPower(2)).map(timesThree)
numbers.next() // { value: 0, done: false }
numbers.next() // { value: 75, done: false }  75 = 25 * 3

The generatorFilter and generatorMap functions are hidden inside wrap and exposed through the filter and map properties on the wrapped object. We initialize modifiedGenerator with the generator passed in, and then as calls are made to map and filter, we change the modifiedGenerator and return the wrapped object. From there, it’s really easy to chain calls to get something like multiples of five that are perfect squares, then to multiply them by three.

There’s a lot more you can do with generators. You can pass information into the generator by passing parameters to the next function. You can run generators in tandem and pass control back and forth with yield*. If you’ve got a finite number of items, you can iterate through them with for...in, or you can spread their values into an array or an object: [...someFiniteGenerator].

For more reading on generators, check out the following links:

Mozilla Developer Network – Iterators and Generators

Exploring ES6 – Generators