How I Implemented Lazy Infinite Lists in JavaScript with Proxy

lazy-infinite-lists.js

// How I Used Proxy to Implement Lazy Infinite Lists in JavaScript
// Published on medium.com December 4, 2016 (http://bit.ly/2gVb1k5)
// Example code

// proxy example

class Secret {
  constructor(msg) { this.info = msg }
}

let handler = {
  get: (target, prop) => prop === "info" ? "Too many secrets" : target[prop]
}

let makeSecret = msg => new Proxy(new Secret(msg), handler)

let s1 = new Secret("Confidential information")
let s2 = makeSecret("More confidential information")

// linked list

class List {
  constructor(x, xs) {
    this.head = () => x
    this.tail = () => xs
  }
  [Symbol.iterator]() {
    const listIterator = function* (xs) {
      do {
        yield head(xs)
        xs = tail(xs)
      } while (xs !== emptyList)
    }
    const gen = listIterator(this)
    return {
      next() { return gen.next() }
    }
  }
  valueOf() {
    let value = xs => isEmpty(xs) ? `[]` : `${head(xs)}:${value(tail(xs))}`
    return isEmpty(this) ? `[]` : `[${value(this)}]`
  }
}

// basic list interface

const emptyList = new List()

const isEmpty = xs => xs === emptyList

const cons = (x, xs) => new List(x, xs)

const list = (...as) => as.length === 0 ? emptyList : new List(as.shift(), list(...as))

const head = xs => {
  if (isEmpty(xs)) { throw Error('EmptyListError') }
  return xs.head()
}

const tail = xs => {
  if (isEmpty(xs)) { throw Error('EmptyListError') }
  return xs.tail()
}

// lazy list constructors

const listRange = (start, end) => {
  if (start === end) { return list(start) }
  if (start > end) { return listRangeBy(start, end, x => x - 1) }
  return listRangeBy(start, end, x => x + 1)
}

const listRangeBy = (start, end, step) => {
  if (start === end) { return list(start) }
  let x = start
  const xs = list(x)
  const listGenerator = function*() {
    x = step(x)
    while (start < end ? x < end : x > end) {
      yield list(x)
      x = step(x)
    }
  }
  const gen = listGenerator()
  const handler = {
    get: function(target, prop) {
      if (prop === `tail` && isEmpty(tail(target))) {
        const next = gen.next()
        if (next.done === false) { target[prop] = () => new Proxy(next.value, handler) }
      }
      return target[prop]
    }
  }
  const proxy = new Proxy(xs, handler)
  return proxy
}

// infinite list constructors

const listInf = start => listInfBy(start, x => x + 1)

const listInfBy = (start, step) => listRangeBy(start, Infinity, step)

// basic list functions

const length = xs => {
  const lenAcc = (xs, n) => isEmpty(xs) ? n : lenAcc(tail(xs), n + 1)
  return lenAcc(xs, 0)
}

const index = (as, n) => {
  if (n < 0 || isEmpty(as)) { throw Error('OutOfRangeError') }
  const x = head(as)
  const xs = tail(as)
  if (n === 0) { return x }
  return index(xs, n - 1)
}

const listAppend = (xs, ys) => {
  if (isEmpty(xs)) { return ys }
  if (isEmpty(ys)) { return xs }
  return cons(head(xs), listAppend(tail(xs), ys))
}

const take = (n, as) => {
  if (n <= 0) { return emptyList }
  if (isEmpty(as)) { return emptyList }
  const x = head(as)
  const xs = tail(as)
  return cons(x, take(n - 1, xs))
}

const drop = (n, as) => {
  if (n <= 0) { return as }
  if (isEmpty(as)) { return emptyList }
  const xs = tail(as)
  return drop(n - 1, xs)
}

const map = (f, as) => {
  if (isEmpty(as)) { return emptyList }
  const x = f(head(as))
  const xs = tail(as)
  return cons(x, map(f, xs))
}

// functions on infinite lists

const iterate = (f, x) => listInfBy(x, x => f(x))

const repeat = a => cons(a, listInfBy(a, a => a))

const replicate = (n, x) => take(n, repeat(x))

const cycle = as => {
  if (isEmpty(as)) { throw Error('EmptyListError') }
  let x = head(as)
  let xs = tail(as)
  const c = list(x)
  const listGenerator = function* () {
    do {
      x = isEmpty(xs) ? head(as) : head(xs)
      xs = isEmpty(xs) ? tail(as) : tail(xs)
      yield list(x)
    } while (true)
  }
  const gen = listGenerator()
  const handler = {
    get: function (target, prop) {
      if (prop === `tail` && isEmpty(tail(target))) {
        const next = gen.next()
        target[prop] = () => new Proxy(next.value, handler)
      }
      return target[prop]
    }
  }
  const proxy = new Proxy(c, handler)
  return proxy
} 

// examples
  
const fib = n => n < 2 ? n : fib(n - 1) + fib(n - 2)
const fibs = n => map(fib, take(n, listInf(1)))

const fact = n => n === 1 ? n : fact(n - 1) * n
const facts = n => map(fact, take(n, listInf(1)))

const sqrt = (a0, eps, n) => {
  const within = (eps, rest) => {
    let a = index(rest, 0)
    let b = index(rest, 1)
    return Math.abs(a - b) <= eps ? b : within(eps, drop(1, rest))
  }
  const next = (n, x) => (x + n / x) / 2
  return within(eps, iterate(next.bind(null, n), a0))
}

const booleans = cycle(list(false, true))

// binary tree

class Tree {
  constructor(left, label, right) {
    this.left = () => left
    this.label = () => label
    this.right = () => right
  }
}

const leaf = new Tree()

const node = (left, label, right) => new Tree(left, label, right)

const insert = (x, t) => {
  if (t === leaf) { return node(leaf, x, leaf) }
  if (x === t.label()) { return t }
  if (x < t.label()) { return node(insert(x, t.left()), t.label(), t.right()) }
  return node(t.left(), t.label(), insert(x, t.right()))
}

const preorder = t => t === leaf ? [] : [t.label()].concat(preorder(t.left()).concat(preorder(t.right())))

const inorder = t => t === leaf ? [] : inorder(t.left()).concat([t.label()].concat(inorder(t.right())))

const postorder = t => t === leaf ? [] : postorder(t.left()).concat(postorder(t.right()).concat([t.label()]))