Introducing: Lazy Arrays in JavaScript

June 09, 2017

Today I’m introducing lazy-arr, which brings lazy arrays to JavaScript.

What’s a lazy array and why is it useful?

Flashback to your job interview for your first software engineering job: let’s write a Fibonacci function. We define the base cases of 0 and 1, then recurse to generate the rest:

let fib = (n) => {
  switch (n) {
    case 0:
      return 0
    case 1:
      return 1
    default:
      return fib(n - 1) + fib(n - 2)
  }
}

Easy peezy.

What’s the problem with this solution? Duh - it’s really really inefficient. To compute the nth Fibonacci number, we call fib 2^n-1 times! Clearly that sucks, and we should do better.

One way to do that is to memoize the output of fib. That is, since fib is pure and idempotent we can cache its output:

let memoize = (fn) => {
  let cache = new Map()
  return (_) => {
    if (!cache.has(_)) {
      cache.set(_, fn(_))
    }
    return cache.get(_)
  }
}

let fib = memoize((n) => {
  switch (n) {
    case 0:
      return 0
    case 1:
      return 1
    default:
      return fib(n - 1) + fib(n - 2)
  }
})

Ah, better! Now we call fib just n - 1 times for an input of size n.

How else can we express that?

Lazy sequences

In Scala, you can do it like this (credit to Philipp Gabler):

def fib(n: Int): Stream[Int] = {
  lazy val stream: Stream[Int] = 0 #:: stream.scan(1)(_ + _)
  stream.take(n)
}

What that does is define a lazy stream of numbers (two initial numbers, plus a function that generates more numbers), and when you call fib(n) it returns the nth number, or generates and returns it if it hasn’t been computed yet. Another way to think about that is as a generator plus a cache that keeps track of previously generated values, which you can then access with the value’s index.

Lazy streams are a really cool abstraction for working with sequences that are either expensive to calculate, or impossible to calculate for all indices (ie. infinite sequences). They’re popular in functional languages, especially in languages with lazy evaluation by default. For example here’s how you do it in Haskell:

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

And same idea, but in Clojure:

(defn fib []
  ((fn rfib [a b]
       (cons a (lazy-seq (rfib b (+ a b)))))
    0 1))

You get the picture.

So how do you do that in JavaScript?

Lazy sequences in JavaScript

With lazy-arr, you do it like this:

let fibs = lazy([0, 1])((_) => fibs[_ - 1] + fibs[_ - 2])

That’s it! Then you can access items in the array as needed, and they’ll be computed on demand:

fibs[10] // 55
fibs[7] // 13

That first line computes the 10th Fibonacci number, and since we defined that computation recursively (in terms of previous Fibonacci numbers) we need to compute the first 9 Fibonacci numbers in order to compute the 10th. So when we compute the 7th Fibonacci number on the second line, the result returns instantly, because we’ve already computed it!

The best part is as far as the consumer is concerned, the fibs array doesn’t do anything lazily or statefully or recursively or anything like that. It’s just an array. The yucky stuff is hidden away by lazy-arr, and the generator is a one liner.

Neat, huh?