Datastructures II: Lazy List

In the previous episode we implemented eager linked-list. That wasn't uninteresting but didn't really add anything new to the basic JS toolkit. At least we gained some knowledge and now we're ready to tackle laziness.

Lazy list is the most common lazy datastructure. But we need to recall the very concept of lazy values first. Lazy values are made of thunks:

42       // eager value
() => 42 // lazy value

But what's the reason to put values in thunks to begin with. Well, replace values with computations, and you'll get the answer.

2 + 2       // immediate computation
() => 2 + 2 // suspended computation (thunk)

From the lazy point of view, computations and values become the same thing. Which really does open some new possibilities. We can memoize thunks:

let lazy = (thunk) => memoize(thunk)

let r = lazy(() => heavyComputation())
r() // slow
r() // fast

In languages with static types, it's also a proper place to put a thunk in type container. This lazy function is often called defer or delay. For brevity we won't pass thunks through this function. But it's worth to keep in mind the option of memoization judging the following.

The basis for lazy lists is very simple:

// just like before
function Cons(value, next) {
  return {value, next}
}

let empty = () => null

let singleton = (x) => () => Cons(x, empty)

let prepend = (x, xs) => () => Cons(x, xs)

And usage is very similar to the eager version:

let A3 = () => null
let A2 = () => Cons("a2", A3)
let A1 = () => Cons("a1", A2)
let A0 = () => Cons("a0", A1)

console.log(A0())                      // {value: "a0", next: [Function]}
console.log(A0().next())               // {value: "a1", next: [Function]}
console.log(A0().next().next())        // {value: "a2", next: [Function: empty]}
console.log(A0().next().next().next()) // null

Reimplement the starting kit:

let toArray = (xs) => {
  let _xs = xs()
  if (_xs) {
    return [_xs.value].concat(toArray(_xs.next))
  } else {
    return []
  }
}

let fromArray = (xs) => {
  if (xs.length) {
    return () => Cons(xs[0], fromArray(xs.slice(1)))
  } else {
    return empty
  }
}

let logList = (list) => console.log(toArray(list))

logList(A0) // ["a0", "a1", "a2"]

As you can see, the only differences here are:

Of course you can't use toArray to convert infinite lists to arrays. And we really need to make logList smarter. Which we'll come back to further.

For now, let's reimplement the basics of functional API:

let append = (x, xs) => {
  let _xs = xs()
  if (_xs) {
    return () => Cons(_xs.value, append(x, _xs.next))
  } else {
    return singleton(x)
  }
}

logList(append("a3", A0)) // ["a0", "a1", "a2", "a3"]
let concat = (xs, ys) => {
  let _xs = xs()
  if (_xs) {
    return () => Cons(_xs.value, concat(_xs.next, ys))
  } else {
    return ys
  }
}

logList(concat(A0, A0)) // ["a0", "a1", "a2", "a0", "a1", "a2"]
let map = (fn, xs) => {
  let _xs = xs()
  if (_xs) {
    return () => Cons(fn(_xs.value), map(fn, _xs.next))
  } else {
    return empty
  }
}

logList(map(x => x + "!", A0)) // ["a0!", "a1!", "a2!"]

Is our implementation really capable to describe infinities? Yes! And to prove it, we need just a couple of new constructors:

// 5 => (5, 5, 5, 5 ...)
let repeat = (n) => {
  return () => Cons(n, repeat(n))
}

// (1, 2, 3) => (1, 2, 3, 1, 2 ...)
let cycle = (xs) => {
  return concat(xs, () => cycle(xs)())
}

For simplicity and uniformity, our functions accept only lists and never arrays. Except fromArray, of course. There may be additional implicit requirements, such as accepting only a finite lazy list in cycle. At this level we don't care so much.

Now fasten your belt and observe:

// Spoiler I
let rx = repeat("x")
console.log(rx())                // {value: "x" ...}
console.log(rx().next())         // {value: "x" ...}
console.log(rx().next().next())  // {value: "x" ...}
// ...

// Spoiler II
let ax = cycle(fromArray(["x", "y", "z"]))
console.log(ax())                             // {value: "x" ...}
console.log(ax().next())                      // {value: "y" ...}
console.log(ax().next().next())               // {value: "z" ...}
console.log(ax().next().next().next())        // {value: "x" ...}
console.log(ax().next().next().next().next()) // {value: "y" ...}

Again, at this point we'd like to check our recursive APIs don't really blow up the stack. Because of thunks they shouldn't, but without an option to verify, we skip this topic again.

The better logList:

let take = (n, xs) => {
  let _xs = xs()
  if (_xs && n) {
    return () => Cons(_xs.value, take(n - 1, _xs.next))
  } else {
    return empty
  }
}

let logList = (list) => {
  let a = toArray(take(11, list))
  let s = JSON.stringify(a.slice(0, 10))
  if (a.length > 10) {
    console.log(s.replace(/^\[/, "(").replace(/]$/, "...)"))
  } else {
    console.log(s.replace(/^\[/, "(").replace(/]$/, ")"))
  }
}

In real life, we would separate logging and serialization, but it's fine for a temporal solution.

So finally the official demo:

// Demo I
logList(repeat("x"))) // ("x", "x", "x", "x", "x", "x", "x", "x", "x", "x"...)

// Demo II
logList(cycle(fromArray(["x", "y"])))) // ("x", "y", "x", "y", "x", "y", "x", "y", "x", "y"...)

In the next episode we'll compare lazy lists with generators.