When talking to my peers about the coming features in JavaScript, the most common response I get when talking about iterators and generators, is that they haven’t yet found any value in it.

I don’t know if this is from lack of trying to understand what they are about, or people simply hasn’t gotten around to it yet. Either way, on the top of my head, here are a few things that generators and iterators will help with in the (near) future:

• Asynchronous programming.^{1, 2, 3, 4} This is the biggest, most obvious application for generators that everyone is talking about.
• Infinite data structures.⁵ The typical example you will find here, is an iterator that keeps returning the next fibonacci number.
• Lazy evaluation. This is a non-obvious advantage that you get from working on iterators (rather than arrays), and the one I will focus on below.

Notice: Before reading this, I suggest you at least have a basic understanding of what iterators in JavaScript is.

What is lazy evaluation?

From Wikipedia⁶.

[L]azy evaluation, or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed [...]

So, if we map over an array with some function producing a new array, then (if this is done lazily), the machine will not actually do any work, until we ask for each of the values in this new array. Instead, what it gives us, is a “placeholder” for the new array–a sort of promise that “whenever you need this value, I will produce it for you”.

More from Wikipedia:

Delayed evaluation is used particularly in functional programming languages. When using delayed evaluation, an expression is not evaluated as soon as it gets bound to a variable, but when the evaluator is forced to produce the expression’s value. That is, a statement such as x:=expression; (i.e. the assignment of the result of an expression to a variable) clearly calls for the expression to be evaluated and the result placed in x, but what actually is in x is irrelevant until there is a need for its value via a reference to x in some later expression whose evaluation could itself be deferred, though eventually the rapidly growing tree of dependencies would be pruned to produce some symbol rather than another for the outside world to see.

We won’t be changing how native arrays work, but we’re going to get a similar result as described above, using iterators.

Don’t worry if lazy evaluation isn’t crystal clear in your mind just yet. Hopefully the following example will make it a lot more tangible for you.

The code

Before we get to the lazy way, I’d like to go through the same thing operation, using JavaScript’s built-in filter and find methods for comparison. Let’s start with a list of dogs, and two helper functions.

var dogs = [
    {size: 'S', age: 4, name: 'Alice'},
    {size: 'L', age: 2, name: 'Bob', },
    {size: 'S', age: 7, name: 'Carol'},
    {size: 'L', age: 6, name: 'Dan'},
    {size: 'L', age: 2, name: 'Eve'},
    {size: 'S', age: 2, name: 'Frank'},
    {size: 'S', age: 1, name: 'Grant'},
    {size: 'S', age: 9, name: 'Hans'},
    {size: 'L', age: 8, name: 'Inga'},
    {size: 'L', age: 4, name: 'Julia'}
];

var isLarge = dog => dog.size === 'L',
    isOld = dog => dog.age > 5;

Our goal is to find the first large old dog (“Dan”). Since this is a contrived example, let’s just imagine that this is how we’d do it normally:

dogs.filter(isLarge).find(isOld); // Dan

However this is wildly inefficient. The problem is that the filter traverses the entire array, even though it doesn’t really need to do any work beyond Dan. This is key to understanding, so let me repeat that: Beyond Dan, we do not care who, or how many, is in the array. Once we have found our dog, we got what we need. Job done… so why are we even looking at Eve and all the rest of them?

Here is how it looks, schematically. You can hover the mouse on the steps to see a visual representation of that step.

In a lazily evaluated world, the above “unnecessary steps” will never happen, and this is exactly what we are trying to eliminate.

The lazy way

As I’ve said a few times by now, there is no real trick to this. All we need, are functions (like filter and find) that operate on iterators instead. Let’s build them.

var filter = function* (f, it) {
    for (var x of it)
        if (f(x)) yield x;
};

var find = (f, it) => {
    for (var x of it)
        if (f(x)) return x;
};

That is literally all we need in our arsenal. filter takes a function and an iterator and returns another iterator. find takes similar parameters, but returns a value instead. We can now do

var largeDogs = filter(isLarge, dogs);

find(isOld, largeDogs); // Dan

That’s it. That’s all there is to it. The code above is lazily evaluated. It never touches any of the objects beyond “Dan”, and it does not do any comparison until find is called.

Here is how we might represent what’s going on visually.

The steps to find the right dog are now cut in half and we go through each item in order.

Validating that it is lazy

How do we make sure that this is being lazily evaluated? After all, the return value is the same. We can start by redefining filter:

var filter = function* (f, it) {
    for (var x of it) {
        console.log('filter', f(x), x.name);
        if (f(x))
            yield x;
    }
};

var find = (f, it) => {
    for (var x of it) {
        console.log('find', f(x), x.name);
        if (f(x))
            return x;
    }
};

We added simple console.log statement to see whenever it does its work (the f(v) bit). With the other functions and values as defined previously, let’s try again.

var largeDogs = filter(isLarge, dogs);
// Notice that nothing was logged.

find(isOld, largeDogs);
filter false Alice // logged
filter true Bob    // logged
find false Bob     // logged
filter false Carol // logged
filter true Dan    // logged
find true Dan      // logged
→ {size: "L", age: 6, name: "Dan"}

This little experiment makes it fairly easy to confirm that the operation was indeed lazily evaluated. The filtering function never looked at Eve and beyond.

In a functional world

Lazy evaluation comes from the world of functional programming; so it is only natural to make a quick reference to how this might be used together with composition and currying.⁷ Without going into too much (any) detail (see links at the bottom if you are interested), this is how we could construct a lazy evaluated function that finds the first large old dog in our array.

var findLargeOldDog = compose(find(isOld), filter(isLarge));

// And we can use this to find our dog
findLargeOldDog(dogs); // Dan

Notes & Links

I only covered one aspect of lazy evaluation. The other part is memoization, which a fairly common (or at least well known) pattern in the JavaScript world.

The links below are not all referenced directly in the text above, but I believe you might find them useful nonetheless.

1. github.com/ubolonton/js-csp
2. github.com/casperin/learning
3. github.com/kriskowal/q
4. github.com/tj/co
5. Tim Taubert: Working with infinite sequences in javascript
6. Wikipedia: Lazy evaluation
7. Introduction to using compose and autoCurry
8. MDN: Iterators and Generators
9. Jason Orendorff: ES6 In Depth: Generators
10. Wikipedia: Memoization
11. github.com/casperin/iters.js
12. github.com/casperin/iters-fn—the functional cousin to iters.js.