Javascript: Immutable Collections - Maps

This is a continuation of an earlier post, and I'll be building on the concepts I established there.

Let's move on to another common concept: The Map (Or the Dictionary, if you're use to a language that calls them that). Traditionally, Javascript is built almost entirely on top of maps in the form of objects.

    let a = {};
    a.cool = "dude"; //or a["cool"] = "dude" or like 15 other ways
    console.log(a); // { cool : "dude" }

In this example a is a Javascript object, but it's basic underpinnings are the same as a map. It has a set of unique keys each paired with a non-unique value. Quite useful, to be sure!

But as with nearly all things Javascript, traditional objects are mutable.

    a.cool = "bird";
    console.log(a); // { cool : "bird" }

So what can we do to remedy this? Let's build a simple Immutable Map class in Javascript that functions similarly to our List (in fact, we'll make use of our List as part of it!).

class Map {
  constructor(n) {
    //private variables
    const that = this;
    const m = n ? n : {};
    
    //private methods
    const modify = (func) => {
      const n = Object.assign({}, m);
      func(n);
      return new Map(n);
    }
    
    //priviliged methods
    this.get = (k) => {
      return m[k];
    }
    
    this.put = (k, v) => {
      return modify(n => n[k] = v);
    }
    
    this.remove = (k) => {
      return modify(n => delete n[k]);
    }
    
    this.map = (keyFunc, valueFunc) => {
      let n = new Map();
      that.forEach((key, value) => n = n.put(keyFunc(key), valueFunc(value)));
      return n;
    }
    
    this.forEach = (func) => {
      for (let key in m) {
        if (m.hasOwnProperty(key)) {
          func(key, m[key]);
        }
      }
    }
    
    this.values = () => {
      let l = new List();
      that.forEach((key, value) => l = l.prepend(value));
      return l;
    }
    
    this.keys = () => {
      let l = new List();
      that.forEach((key, value) => l = l.prepend(key));
      return l;
    }
  }
}

OK, let's take a look at what's actually happening here. We'll break it down step by step! First we'll take a look at the constructor.

constructor(n) {
    //private variables
    const that = this;
    const m = n ? n : {};

Obviously the "constructor" makes up the entire class but we'll deal with the privileged methods later. The constructor itself takes in n, an object. This, in the form of m, is the backing object for our array and functions as the actual Map. We keep this private to the constructor's closure to prevent being able to access it outside the context (Though it should be noted that if you manually pass in n rather than calling the default constructor that the initial Map object functions as a VIEW of the original object until you perform a modifying action and receive a new Map object meaning that modifying n will modify the object in the Map). The rest of our methods are going to interact with this object in some way. that is a private copy of this because the scoping of this changes inside of functions declared within the constructor.

Now that we've established how we're backing this object the next obvious (and easiest) method to talk about is get(k).

this.get = (k) => {
  return m[k];
}

This method is straight forward. Given a key we ask to pull it off m. If the object doesn't exist undefined is returned instead. Simple! But what about modification methods?

const modify = (func) => {
  const n = Object.assign({}, m);
  func(n);
  return new Map(n);
}

this.put = (k, v) => {
  return modify(n => n[k] = v);
}

this.remove = (k) => {
  return modify(n => delete n[k]);
}

put(k, v) and remove(k) are the standard set of modification methods available on a map. put(k, v) adds a new value to the Map (or replaces an existing key), while remove(k) removes a value from the Map. You will notice both of these methods do two things in common: They copy all values of m into a new object n, and they return a new Map(n), which we've extracted out to the private method modify(func). By copying all the object from m to n, we're creating a new object that is identical to our original object, but we're free to modify by adding or removing a key. This way the original Map doesn't change, but we end up with a new Map that reflects our change. We have one last modification method to address:

this.map = (keyFunc, valueFunc) => {
  let n = new Map();
  that.forEach((key, value) => n = n.put(keyFunc(key), valueFunc(value)));
  return n;
}

map allows us to modify every key-value in the same way to create a new Map reflecting the updated version. This method is your typical mapping function, and it makes use of our forEach(func) method. Just like put(k, v) and remove(k) this method performs no modifications on the original Map object. But what about the forEach method?

this.forEach = (func) => {
  for (let key in m) {
    if (m.hasOwnProperty(key)) {
      func(key, m[key]);
    }
  }
}

This method is very straight forward. We take each key in m, make sure that the key belongs to m and not the Object prototype, and perform the function against it. This also let's us create our last two utility methods, values() and keys(), which simply return a List of the keys or values of the map.

There you have it! With this prototype we have a very basic immutable map. Just like with the immutable list we created last time we can now safely modify a map without working about how it effects references to the original map in other objects. To go back to our original example:

    let a = new Map();
    a = a.put('cool', 'dude');
    console.log(a.get('cool')); // 'dude'
    a.put('cool', 'bird'); //If we don't reassign "a" to the returned value, we don't see the change
    console.log(a.get('cool')); // 'dude'

About the author
Photo by Stephen Monroe on Unsplash