List

List.js

class List {
  constructor() {
    this.arr = undefined;
    this.length = 0;
    this.inLength = 0;
    this.dirty = false;
    this.prev = undefined;
  }

  push(v) {
    const l = new List();
    l.length = this.length + 1;
    if (!this.dirty) {
      const arr = this.arr ? this.arr : [];
      arr.push(v);
      l.arr = arr;
      l.inLength = this.length + 1;
      this.dirty = true;
    } else {
      l.arr = [v];
      l.inLength = 1;
      l.prev = this;
    }

    return l;
  }

  * iter() {
    this.dirty = true;
    const { arr = [] } = this;
    for (let i = this.inLength - 1; i >= 0; i -= 1) {
      yield arr[i];
    }

    if (this.prev) {
      yield* this.prev.iter();
    }
  }
}

const Nil = new List();

module.exports = Nil;

const l1 = Nil.push(1);
const l2 = l1.push(2);
const l3 = l2.push(3);
const l2a = l2.push('foo');

console.log(Nil, l1, l2, l3, l2a);
console.log(Array.from(Nil.iter()));
console.log(Array.from(l1.iter()));
console.log(Array.from(l2.iter()));
console.log(Array.from(l3.iter()));
console.log(Array.from(l2a.iter()));

/*
[]
[ 1 ]
[ 2, 1 ]
[ 3, 2, 1 ]
[ 'foo', 2, 1 ]
*/