linguistics, computers, and puns

# 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.

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)))
``````
1. `(range)` with no arguments produces an infinite sequence of non-negative integers.
2. `(filter odd? ...)` gives us an infinite sequence of only the odd integers.
3. `(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 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.

Clojure's `(range)`, on the other hand, was able to give us just the first 100 values (200 before `filter`ing) 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 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

1. 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.

2. 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.