From time to time I like to go back to the fundamentals and play around with basic concepts. This serves to keep myself sharp as well as provide an opportunity to explore some concepts in greater detail than what I was able to do previously. I was doing that recently with an implementation of an immutable list in JavaScript (similar to what you would find in immutablejs). Things were going well enough with my super basic implementation when I started thinking about how you would hide implementation details and how you could implement an iterator for my list data structure.

Before jumping into the code, it’s worth noting a few things. First, I’m using ES2018 syntax with the class properties proposal. I am also using Flow Types because I like the static analysis options that it provides and I think it adds some additional clarity on the intent of the code. Finally, this code is NOT meant to be production ready and is missing many optimizations that would make it truly useful. This is meant to be used for educational purposes only. You have been warned.

So now that we have that out of the way, the initial implementation of my immutable list looks like this:

export class ImmutableList<Type> {
    _elements: Type[] = [];

    get length(): number {
        return this._elements.length;
    }

    add(value: Type): ImmutableList<Type> {
        const newList = this._copy();

        newList._elements.push(value);

        return newList;
    }

    insert(value: Type, index: number): ImmutableList<Type> {
        if (index < 0 || index > this.length) {
            throw new Error(`Index out of bounds: ${index}`);
        }

        const newList = this._copy();
        newList._elements.splice(index, 0, value);

        return newList;
    }

    get(index: number): Type {
        if (index < 0 || index >= this.length) {
            throw new Error(`Index out of bounds: ${index}`);
        }

        return this._elements[index];
    }

    remove(index: number): ImmutableList<Type> {
        if (index < 0 || index >= this.length) {
            throw new Error(`Index out of bounds: ${index}`);
        }

        const newList = this._copy();
        newList._elements.splice(index, 1);

        return newList;
    }

    _copy(): ImmutableList<Type> {
        const clone = new ImmutableList();
        clone._elements = [...this._elements];

        return clone;
    }

    // TODO: iteration
}

So what does this code do? It implements a simple list structure that has a length property which says how many elements it contains, has a few methods for mutating the data (add, insert, and remove methods) that can be used to create a duplicate list with the corresponding change, and a get method for accessing elements at specific indices. Pretty simple right?

So one of the things that irks me about this (and is a general problem with languages like Python and JavaScript) is that we have kind of exposed some implementation details. Namely a user of this class could directly access the underlying data (_elements) and the method we use to copy the list (_copy). Exposing the copy method isn’t the worst, just awkward, but exposing _elements breaks the fundamental premise of the structure. A user could directly modify the list and lose the immutable constraint. This is not ideal.

Now someone that’s been working with JavaScript for a while might say, “Why not just wrap everything in a function and protect things with a closure?” Sure that certainly works and would solve the problem. This would look something like:

export interface ImmutableList<Type> {
    get length(): number;

    add(value: Type): ImmutableList<Type>;
    insert(value: Type, index: number): ImmutableList<Type>;
    get(index: number): Type;
    remove(index: number): ImmutableList<Type>;
}

function newImmutableListImpl<Type>(elements: Type[]): ImmutableList<Type> {
    class ImmutableListImpl implements ImmutableList<Type> {
        get length(): number {
            return elements.length;
        }

        add(value: Type): ImmutableList<Type> {
            return newImmutableListImpl([...elements, value]);
        }

        insert(value: Type, index: number): ImmutableList<Type> {
            if (index < 0 || index > this.length) {
                throw new Error(`Index out of bounds: ${index}`);
            }

            const newElements = [...elements];
            newElements.splice(index, 0, value);

            return newImmutableListImpl(newElements);
        }

        get(index: number): Type {
            if (index < 0 || index >= this.length) {
                throw new Error(`Index out of bounds: ${index}`);
            }

            return elements[index];
        }

        remove(index: number): ImmutableList<Type> {
            if (index < 0 || index >= this.length) {
                throw new Error(`Index out of bounds: ${index}`);
            }

            const newElements = [...elements];
            newElements.splice(index, 1);

            return newImmutableListImpl(newElements);
        }

        // TODO: iteration
    }

    return new ImmutableListImpl();
}

export function newImmutableList<Type>(): ImmutableList<Type> {
    const elements: Type[] = [];

    return newImmutableListImpl(elements);
}

We’ve created a new function (newImmutableList) which creates a list instance (rather than calling new ImmutableList()). This in turn calls the internal function that actually does the work (newImmutableListImpl) and creates the closure which protects the stuff we want to hide. But now the thing that bothers me about this is that it necessitates the creation of a new class on every single call to create a list. This feels like serious overkill to me. I almost feel like there’s no reason to have a class when you don’t actually get the memory and performance benefits of a single implementation. I’m sure there are ways to make this simpler and reduce the impact but I can’t imagine that the intent of the original code would remain anymore. I’m just not a fan of this methodology.

So if that method is out, what can we use?

Lucky enough, there’s a nifty feature that was added a while back to JavaScript called Symbols. Symbols are a new primitive that basically function like globally unique values (I’m ignoring the Symbol.for method). Every instance you create will be completely unique from any other. So how does this help us?

Think of a class as a a normal object (which it pretty much is) which means that we can also treat it like a normal map data structure of some key to some value. That value might be a function (method) or a value (property/attribute). Normally the type of key that you would use to reference a method or property of a class is a string. This means that effectively if you had some instance of a class named foo and a method on that class called bar, you could reference that method in one of two ways. You could do the more intuitive foo.bar() or you could do foo['bar'](). The last one is the key. We could change the type that we use to get the desired method/property from string to symbol and generate a symbol at runtime. This means that every time the code is loaded, a new name for what we want to hide is generated with no way of stealing a copy of that name.

So we just need to create two symbols that we can use to reference our internal list and the copy method and we have effectively hidden our implementation with very little work and minimal loss of readability.

const elementsSymbol = Symbol();
const copySymbol = Symbol();

export class ImmutableList<Type> {
    constructor() {
        // $FlowFixMe
        this[elementsSymbol] = [];
    }

    get length(): number {
        // $FlowFixMe
        return this[elementsSymbol].length;
    }

    add(value: Type): ImmutableList<Type> {
        // $FlowFixMe
        const newList = this[copySymbol]();

        newList[elementsSymbol].push(value);

        return newList;
    }

    insert(value: Type, index: number): ImmutableList<Type> {
        if (index < 0 || index > this.length) {
            throw new Error(`Index out of bounds: ${index}`);
        }


        // $FlowFixMe
        const newList = this[copySymbol]();
        newList[elementsSymbol].splice(index, 0, value);

        return newList;
    }

    get(index: number): Type {
        if (index < 0 || index >= this.length) {
            throw new Error(`Index out of bounds: ${index}`);
        }

        // $FlowFixMe
        return this[elementsSymbol][index];
    }

    remove(index: number): ImmutableList<Type> {
        if (index < 0 || index >= this.length) {
            throw new Error(`Index out of bounds: ${index}`);
        }

        // $FlowFixMe
        const newList = this[copySymbol]();
        newList[elementsSymbol].splice(index, 1);

        return newList;
    }

    // $FlowFixMe
    [copySymbol](): ImmutableList<Type> {
        const clone = new ImmutableList();
        clone[elementsSymbol] = [...this[elementsSymbol]];

        return clone;
    }

    // TODO: iteration
}

I will say that it does bother me that Flow doesn’t support dynamic property names. I kind of get the reasoning (how can we statically analyze something that’s by definition not static) but for real, this would be really nice.

Anyway, we’ve solved that problem. Now how do we make this data structure iterable? This actually works pretty much the same way as how we hide our implementation details, with symbols!

The symbol class has a set of constants on it that the browser assigns special meaning to when it finds them on an object. One such constant is Symbol.iterator which tells the browser that the class can return an iterator when you call the function that is mapped to the Symbol.iterator key. So what does this look like in practice (in our case anyway)?

const elementsSymbol = Symbol();
const copySymbol = Symbol();

export class ImmutableList<Type> {
    constructor() {
        // $FlowFixMe
        this[elementsSymbol] = [];
    }

    get length(): number {
        // $FlowFixMe
        return this[elementsSymbol].length;
    }

    add(value: Type): ImmutableList<Type> {
        // $FlowFixMe
        const newList = this[copySymbol]();

        newList[elementsSymbol].push(value);

        return newList;
    }

    insert(value: Type, index: number): ImmutableList<Type> {
        if (index < 0 || index > this.length) {
            throw new Error(`Index out of bounds: ${index}`);
        }


        // $FlowFixMe
        const newList = this[copySymbol]();
        newList[elementsSymbol].splice(index, 0, value);

        return newList;
    }

    get(index: number): Type {
        if (index < 0 || index >= this.length) {
            throw new Error(`Index out of bounds: ${index}`);
        }

        // $FlowFixMe
        return this[elementsSymbol][index];
    }

    remove(index: number): ImmutableList<Type> {
        if (index < 0 || index >= this.length) {
            throw new Error(`Index out of bounds: ${index}`);
        }

        // $FlowFixMe
        const newList = this[copySymbol]();
        newList[elementsSymbol].splice(index, 1);

        return newList;
    }

    // $FlowFixMe
    [copySymbol](): ImmutableList<Type> {
        const clone = new ImmutableList();
        clone[elementsSymbol] = [...this[elementsSymbol]];

        return clone;
    }

    // $FlowFixMe
    [Symbol.iterator](): Iterable<Type> {
        return this[elementsSymbol].values();
    }
}

In this case we can use the Array class' iterator in place of making our own from scratch. Usage of our class becomes really simple and intuitive.

let myList = new ImmutableList();
// Add some stuff to it

for (let value of myList) {
    // Do some stuff on each element
}

someFunction([...myList]);

We now have a decent immutable list implementation that hides it’s internal implementation details AND has iterator support all without any terribly complicated changes!