Infinite Sequences in JavaScript

Tim Hammerquist July 06, 2021 #clojure #deepdive #interview #javascript #lazy #typescript

Consider this classic interview question:

Write a function to return the first n odd numbers.

Just reading that, some readers will probably have started answering in their heads already.

What solution you envision will undoubtedly vary, but my Clojure clawed its way to the top:

(defn n-odds [n]
  (->> (range)
       (filter odd?)
       (take n)))

(partition 10 (n-odds 100))

I used the ->> threading macro to make it easier to see what's being done. De-sugared we get:

(take n (filter odd? (range)))

(range) with no arguments produces an infinite sequence of non-negative integers.
(filter odd? ...) gives us an infinite sequence of only the odd integers.
(take n ...) "takes" and returns only the first n elements of the sequence.

A Wry Old-Fashioned

Clojure is designed to be able to handle infinite sequences like this efficiently.

Unfortunately, even modern JavaScript[1] isn't so enlightened. Let's do this the old-fashioned way.

// a simple pretty-printer for iterables
// (it: Iterator<T>) => string
function ppi(it) {
  return Array.from(it).join(', ');
}

// (n: number) => number[]
function eagerOdds(n) {
  const results = [];
  let i = 1;
  while (n-- > 0) {
    results.push(i);
    i += 2;
  }

  return results;
}

ppi(eagerOdds(10));

A pretty straight-forward implementation. And like a lot of other implementations found online, this solution will grind to a halt if we try to use it on an infinite (or even very large) input.

This is because the resulting sequence is generated eagerly; that is, the code attempts to generate every last value before returning even the first.

Bad Religion's 6th Album

Clojure's (range), on the other hand, was able to give us just the first 100 values (200 before filtering) almost instantly. This is possible due to lazy evaluation.

ECMAScript 2015 introduced several features that since made JavaScript development much easier:

lexical variable qualifiers let and const
arrow functions: const add2 = (n) => (n + 2);
module support with import and export syntax
the much-improved for ... of syntax
Iteration protocols

With iteration protocols we get built-in language support for lazy sequence generation. In this case we'll use a Generator to produce our ranges.

And because a Generator implements the iterable protocol, we can use it in a for ... of loop just like an Array.

Here's our range() implementation.

// (start: number, end: number, step: number = 1) -> Generator<number>
function* range(start, end, step = 1) {
  for (let i = start; i < end; i += step)
    yield i;
}

ppi(range(0, 60, 5));

Take Me On

We can't consume all of an infinite sequence. We'll need a way to limit how much we consume. We could continue to use while/break, but I think take() is a little easier to work with.

Here's take() along with our very first infinite generator, naturals():

// <T>(n: number, Iterator<T>) => Generator<T>
function* take(n, it) {
  while (n-- > 0) {
    const result = it.next();
    if (result.done) break;
    yield result.value;
  }
}

// (start?: number) -> Generator<number>
function* naturals(start = 0) {
  while (true) yield start++;
}

ppi(take(10, naturals()));

You've probably seen similar functions in the past, but note the following important features:

function* rather than the usual function
yield to return discrete values, instead of returning a single array

A function defined with the keyword function* returns an Iterator, and a function* that uses the keyword yield returns a Generator — a special case of Iterator.

Handcrafted Filter

The JavaScript Array object provides a built-in filter() method, but arrays are eagerly evaluated. If we tried to call Array.from(range()), the JavaScript process would run away trying to fit every natural number into an array.

Let's roll our own filter() that can work with potentially infinite iterables.

// <T>(f: (x: T) => boolean, it: Iterator<T>) -> Generator<T>
function* filter(f, it) {
  let result = it.next();

  while (!result.done) {
    if (f(result.value)) yield result.value;

    result = it.next();
  }
}

// (n: number) -> boolean
const isOdd = (n) => (n % 2 !== 0);

const oddNumbers = filter(isOdd, naturals());

for (const _ of range(0, 10)) {
  const next10 = take(10, oddNumbers);
  console.log(ppi(next10));
}

Given these functions, we can now generate a lazy sequence of odd integers. Notice that the iterator created in line #1 can be iterated over any number of times and the values will continue where they left off.

Pass me no iterators, I'll yield you no fibs

range() is fine, but there are other infinite series in the Maths sea. Here's a generator for the Fibonacci series.

// () -> Generator<number>
function* allTheFibs() {
  for (let [m, n] = [1, 1];; [m, n] = [n, m + n])
    yield m;
}

ppi(take(10, allTheFibs()));

With just a couple more functions, we have even more ways to elegantly consume the series.

// <T>(n: number, it: Iterator<T>) -> Iterator<T>
function drop(n, it) {
  while (n-- > 0) {
    const result = it.next();
    if (result.done) break;
  }

  return it;
}

// <T>(n: number, it: Iterator<T>) -> T
function nth(n, it) {
  return take(1, drop(n - 1, it)).next().value;
}

// (n: number) -> number
function fib(n) {
  return nth(n, allTheFibs());
}

// the 1,337th number in the Fibonacci series (maybe)
fib(1337);

Okay, I can't vouch for that value. Double-precision floating point values can only get so big without losing precision.

If your browser supports it, this should give us a much more accurate representation of the 1,337th Fibonacci number:

function* bigFibs() {
  for (let [m, n] = [1n, 1n];; [m, n] = [n, m + n])
    yield m;
}

nth(1337, bigFibs()).toString()

This shows[2] that the native number result is accurate to about 16 significant digits, which isn't bad. But that's 16 out of almost 300 digits, so even double-precision FP has lost us a lot of precision.

You might have noticed this is almost identical to the number implementation save for those n suffixes on the literals. Take care, however, when filtering; bigint values are only loosely equal to number values. That is, 0n == 0, but 0n !== 0.

To Infinity ... Possibly

There is some overhead with Iterators and Generators, both in terms of processing and complexity. But for cases where data is slow or expensive to generate, and especially if you may not use the product of all that work, lazy sequences can be a huge win.

I encourage everyone to learn more about the inner workings of the tools they use every day. In this case, the use of the Iterator, Generator, and other iterable types.

There are many other solutions, however, that might make even more sense in your everyday code. Frameworks like Angular and RxJS use Observables for similar use cases. It's a fascinating abstraction that I recommend looking into, even if you aren't an Angular user.

Footnotes

This blog post contains live JavaScript so you can play with the code samples, and to demonstrate that these examples work with vanilla ECMAScript 2015 (a.k.a. "es6"). If your browser doesn't support ES2015, you might miss the interactive experience, but these features can still be achieved by transpiling.

You can find the original TypeScript implementation with full type signatures in the blogcode.
Note the explicit .toString() call. While our browsers might support the bigint type, Klipse — the JavaScript library used to embed these scripts in the browser — apparently doesn't. We call .toString() to ensure the browser engine converts the value to a type Klipse can handle.