Infinite Sequences in JavaScript
July 06, 2021 #Clojure #ClojureScript #Deep Dive #Interviews #JavaScript #Lazy #TypeScriptConsider 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 the sequence of operations.
De-sugared we get:
(partition 10 (take 100 (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 firstn
elements of the sequence.(partition 10 ...
just breaks up the list into chunks of 10 to keep the results from running off-screen!
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 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
andconst
- arrow functions:
const add2 = (n) => (n + 2);
- module support with
import
andexport
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 usualfunction
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 thebigint
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.