Javascript Snippets: Immutable Lists

With the recent popularity of view frameworks such as React and Mercury, immutable data structures have become widespread choices for storing UI state. In this short post, we’ll examine the motivation for maintaining immutability and build a simple snippet for constructing reasonably performant immutable lists. For production usage, check out Facebook’s immutable.js.

Why Immutability?

In various view frameworks, view functions are just plain Javascript functions which take a object representing state and return a virtual HTML tree:

function listView(list) {
  return h('ul', list.map(item => h('li', item)));
}

If listView is used as a component of a large web-app, the list argument may be a nested property of a more complex state object. When the contents of list change, we want to re-render the list to reflect the new state, but when other properties of that object change, it would be nice to not have to re-compute the list view.

In the second case, how can we see if the list argument has changed in a performant fashion? If list is a plain Javascript array and gets mutated elsewhere by list[i] = val, then the equality value of list itself has not changed. Thus, we can’t do a simple object equality === check but instead need the previous contents of the list, and equality checking would be $O(n)$ in the length of the list.

Instead, we may be willing to take a slight performance hit on gets, sets, and iteration as long as equality checking takes constant time. We can use immutable data structures: structures type of T such that T.set returns a new object of type T (if the set changes the contents).

A Naive Implementation

Below is a naive implementation where the list is copied

class List {
  constructor(array) {
    this.array = array;
  }

  get(key) {
    return this.array[key];
  }

  set(key, val) {
    var newArray = this.array.slice();
    newArray[key] = val;
    return new List(newArray);
  }

  iter*() {
    for (var i = 0; i < this.array.length; i++) {
      yield this.array[i];
    }
  }
}

Note here that while get is $O(1)$, set is $O(n)$ in the length of the list. Can we do better?

Trees

How can we improve the performance of set? Note that above, we are forced to copy the entire list into a new list. If we change our underlying data structure from a flat list to a tree, it turns out that we can get $O(\log n)$ sets.

There are two caveats: the first is that using trees slows gets to $O(\log n)$, and the second is that we incur a possibly nontrivial constant factor (around equal to branch size) for sets since we must copy the unchanged children of every tree node we touch.

var BRANCH = 8;
var BRANCH_EXP = 3; // 2^3 = 8 - used for bit shifts.
class Tree {
  constructor() {
    this.children = [];
    this.depth = 0;
  }

  get(key) {
    if (this.depth === 0 && key < BRANCH) {
      return this.children[key];
    } else {
      var shift = BRANCH_EXP * this.depth;
      var childSize = 1 << shift;
      return this.children[key >>> shift].get(key % childSize);
    }
  }

  set(key, val) {
    var newChildren = this.children.slice();
    if (this.depth === 0 && key < BRANCH) {
      newChildren[key] = val;
    } else {
      var shift = BRANCH_EXP * this.depth;
      var childSize = 1 << shift;
      var childIndex = key >>> shift;
      newChildren[childIndex] = newChildren[childIndex].set(key % childSize, val);
    }
    return newChildren;
  }
}

We can now define the List class as follows:

class List {
  constructor(array) {
    if (array isinstance Tree) {
      this.tree = array;
    } else {
      this.tree = makeTree(array);
    }
  }

  get(key) {
    return this.tree.get(key);
  }

  set(key, val) {
    return new List(this.tree.set(key, val));
  }

  iter*() {
    // Inorder transversal of tree.
  }
}

Next Steps

There are lots of performance improvements which can be made over the previous section’s code, which was written with a goal of concision. In a future post, we’ll examine some of these and do some performance testing.