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
nelements of the sequence.
A Wry Old-Fashioned
Clojure is designed to be able to handle infinite sequences like this efficiently.
// a simple pretty-printer for iterables // (it: Iterator<T>) => string // (n: number) => number 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
(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
- lexical variable qualifiers
- arrow functions:
const add2 = (n) => (n + 2);
- module support with
- the much-improved
for ... ofsyntax
- 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
// (start: number, end: number, step: number = 1) -> Generator<number> 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
break, but I think
is a little easier to work with.
take() along with our very first infinite generator,
// <T>(n: number, Iterator<T>) => Generator<T> // (start?: number) -> Generator<number> 10, ;
You've probably seen similar functions in the past, but note the following important features:
function*rather than the usual
yieldto 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
Array object provides a built-in
filter() method, but arrays
are eagerly evaluated. If we tried to call
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> // (n: number) -> boolean ; ; for of 0, 10
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> 10, ;
With just a couple more functions, we have even more ways to elegantly consume the series.
// <T>(n: number, it: Iterator<T>) -> Iterator<T> // <T>(n: number, it: Iterator<T>) -> T // (n: number) -> number // the 1,337th number in the Fibonacci series (maybe) 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:
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
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
Generator, and other
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.
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
.toString()to ensure the browser engine converts the value to a type Klipse can handle.