Infinite Data Structures & Lazy Evaluation in JavaScript

#javascript #webdev #tutorial

Haskell's lazy evaluation is a powerful tool of this functional language that allows its users to break down problems more easily.

Today I'm going to show you how to leverage lazy evaluation by implementing an infinite array using a generator function.

Generator function

function* from(start) {
    while (true) {
        yield start;

        start++;
    }
}

console.log(from(5)); // ???

What do you think this code will output? At first, it seems like we are creating an infinite loop inside our from function. So it seems logical to say that this script will freeze and break. But it will not. Thanks to generator functions. Here is the output.

Object [Generator] {}

A generator function is a special kind of function that will return its value only when needed. This is kind of similar to lazy evaluation in Haskell. Things get evaluated only when needed.

Take

But an infinite generator would be pointless if we couldn't grab some values from it. And since this generator function will return an iterator, it would require a function capable of handling such data structure.

This is why we will need to create a function to handle this. I'm stealing the concept shamelessly from Haskell by creating my own implementation of the take function.

function take(count, generator) {
    const result = [];

    while (count--) {
        result.push(generator.next().value);
    }

    return result;
}

console.log(take(5, from(1))); // [ 1, 2, 3, 4, 5 ]

This function will take as much values from that infinite iterator as needed. Here we only need 5 items so it returns an array of 5 elements starting from 1.

Sum

Look! Now we have something we are used to. A simple array. Let's create a simple function to sum it up!

function sum(array) {
    return array.reduce((total, number) => total + number);
}

console.log(sum(take(5, from(1)))); // 15

Since this is an array, it allows us to use the power of the Array prototype and call the reduce method to get the sum of this array. Simple enough.

With this simple technique, it is easy to compute the sum of the first 10 numbers starting from 5 for instance.

console.log(sum(take(10, from(5)))); // 95

Conclusion

We saw how to implement an interesting data structure which is the infinite list in JavaScript by using a generator function. Generator functions, in combination with iterators, is a concept that once mastered can be really powerful to use in JavaScript.

I suggest you get familiar with these two concepts by reading the documentation.

How do you use generators? Let me know in the comment section.

Be lazy!

Top comments (4)

Jared Beach • Jan 27 '20 • Edited

I’m missing the benefit of the generator over a regular function returning a list

Amin • Jan 27 '20 • Edited

You could have an asynchronous generator function that cycle through all users in an API like JSONPlaceholder. This data structure is theoretically infinite because you don't know how many users are included in this API (well, in fact you can, but let's pretend).

So you could build a generator to return a promise listing all users. With the for-await loop, you could search for a specific user. This is great because it reduces the amount of memory needed to store the users.

"use strict";

async function* users() {
    let index = 1;

    while (true) {
        const response = await fetch(`https://jsonplaceholder.typicode.com/users/${index}`);

        if (!response.ok) {
            break;
        }

        const user = await response.json();

        yield user;

        index++;
    }
}

async function main() {
    for await (const user of users()) {
        if (user.email.includes("net")) {
            console.log(`${user.name} is a .NET user... Just kidding :)`);
            break;
        }
    }
}

main();

In this example, I have only fetched 3 users before finding the one I'm interested in. Whereas with a simple array, you would have requested for the entire database. Then you would have cycled through all of them, only to find that you needed the third one, leaving thousands in memory for nothing. This might not be the best case to illustrate what I'm trying to explain but generator functions are best to describe infinite data structures that would normally overflow the memory, or in the best case slow down the app a lot.