Datastructures III: Lazy List vs Generator

In the previous episode we implemented lazy lists. It's time to compare them with generators which are what many people associate with lazy evaluation in current JavaScript. To be honest, generators are more sophisticated as they allow to pass data in both directions. From producer to consumer and vice-versa, which opens the door to coroutines and other cool async techniques.

But can lazy lists be on par with generators for unidirectional evaluations? Let's find out. This time I omit the lazy list implementation for brevity.

To start, we need the same basic helpers for generators:

let takeIter = (n, iter) => {
  let xs = []
  for (let x of iter) {
    xs.push(x)
    if (xs.length >= n) {
      break
    }
  }
  return xs
}

(compare with)

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

Both version are different but the complexity is the same. Hard to say which one is visually better.

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

(compare with)

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(/]$/, ")"))
  }
}

Sameness of the same. Now we can finally write and compare generative functions.

Natural Numbers

let naturalsGen = function* () {
  let n = 1
  while (true) {
    yield n++
  }
}

let naturalsList = (n = 1) => {
  return () => Cons(n, naturals(n + 1))
}

logIter(naturalsGen())  // (1, 2, 3, 4, 5 ...)
logList(naturalsList()) // (1, 2, 3, 4, 5 ...)

Fibonacci

let fibonacciGen = function* () {
  let f1 = 1
  let f2 = 1
  while (true) {
    yield f1
    yield f2
    let s = f1 + f2
    f1 = f2
    f2 = s
  }
}

let fibonacciList = () => {
  function go(f1, f2) {
    return () => Cons(f2, go(f2, f1 + f2))
  }
  return () => Cons(1, go(1, 1))
}

logIter(fibonacciGen())  // (1, 1, 2, 3, 5 ...)
logList(fibonacciList()) // (1, 1, 2, 3, 5 ...)

Pascal's Triangle

Wiki. This triangle is a well-known mathematical object with the following structure:

     1
    1 1
   1 2 1
  1 3 3 1
 1 4 06 4 1
1 5 10 10 5 1

The numbers at both edges are all 1, and each number inside the triangle is the sum of the two numbers above it.

let R = require("ramda")

// [[a, b], [c, d]] => [a + b, c + d]
let sumPairs = R.map(([x1, x2]) => x1 + x2)

// [a]    => [[0, a], [a, 0]]
// [a, b] => zip([0, a, b], [a, b, 0]) => [[0, a], [a, b], [b, 0]]
let pair = (xs) => R.zip(R.concat([0], xs), R.concat(xs, [0]))

function* pascalRowGen(prevRow) {
  if (prevRow.length) {
    let res = sumPairs(pair(prevRow))
    yield res
    yield* pascalRowGen(res)
  } else {
    yield [1]
    yield* pascalRowGen([1])
  }
}

logIter(pascalRowGen([])) // ([1], [1, 1], [1, 2, 1] ...)
function pascalRowList(prevRow) {
  if (prevRow.length) {
    let res = sumPairs(pair(prevRow))
    return () => Cons(res, pascalRowList(res))
  } else {
    return () => Cons([1], pascalRowList([1]))
  }
}

logList(pascalRowGen([])) // ([1], [1, 1], [1, 2, 1] ...)

And now, just for fun:

console.time("generator")
logIter(pascalRowGen([]))
console.timeEnd("generator")

console.time("lazy-list")
logList(pascalRowList([]))
console.timeEnd("lazy-list")
generator: 3.590ms
lazy-list: 0.719ms

Curious. Even this very straightforward list implementation, which honestly didn't take much thoughts, outperforms generators by a factor of five! If you're performance geek this may be something to consider.

On this note, we end the topic of linked lists and turn our attention to streams. Meanwhile I recommend you to work out the matherial of this three articles and experiment on your own. Stream patterns will look very similar and recursions won't go away for sure.