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

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 *n*th 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?

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 `n`

th 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?

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?

View repo on GitHub ➜lazy-arrPosted...

- By Boris Cherny
- 2 years ago
- In JavaScriptFunctional ProgrammingClojureScalaHaskell