Javascript: Immutable Collections - Lists
I love immutability.
There. I said it. I'm a Java and Javascript developer who LOVES immutable constructs. If I had it my way both languages would be immutable by default. Both would have better support for functional constructs and declarative programming. Both would be more like Kotlin.
But I'm not in charge. I'm just another developer out there in the world doing his thing, unable to make large sweeping changes to languages. Luckily, we're still talking about programming, so while I can't make a major change to the language, I CAN build libraries to at least mitigate what I don't like! So given that preamble, let's talk about immutable collections in Javascript.
"Collections" is a term that is heavily ingrained in me from Java. It specifically refers to a set of data structures that in Java extend the Collection interface, and generally unless you're talking about them in a technical sense also tends to include Maps. The most simple form of a Collection is a List, an array-like construct that maintains insertion order but can be dynamically sized and resized on the fly. Obviously, when looking at such an object definition in Javascript I'm just describing a simple Array.
let arr = []; //Array, sized to zero
arr.push(1); //Array, dynamically resized to 1 to accomodate the new element
arr.push(2); //Array, dynamically resized to 2 to accomodate the new element
console.log(arr); //[1, 2], insertion order maintained!
These two data structure, the Java List and the Javascript Array are one of the backbones of the language and are critical concepts to understand. That doesn't mean that I don't take issue with their implementation though.
The Javascript Array is a mutable data structure. Mutability is defined as "Being able to be mutated", as in "The object is capable of changing it's internal state or having it's internal state changed from outside." There are clear benefits to mutability, especially in performance, but these mutable structures also have their downside. As an example, let's talk about Array.reverse.
let arr = [1,2,3,4,5];
arr.reverse();
console.log(arr); //prints [ 5, 4, 3, 2, 1 ]
Great! Reverse took the array, reordered the values internally, and every subsequent access to arr works against the now reversed array. That doesn't seem so bad on the surface, but let's look at an example where this causes a real problem.
const printReverseArray = (a) => console.log(a.reverse());
const printArray = (a) => console.log(a);
let arr = [ 1, 2, 3, 4, 5 ];
printReverseArray(arr); //Prints [ 5, 4, 3, 2, 1 ], yay!
printArray(arr); //Prints [ 5, 4, 3, 2, 1 ], wait what?!?
Because we altered the internal state of the array in printReverseArray we can't act safely on it afterwards. printReverseArray is an unsafe method! Yes, we could protect against this by copying the array to a new variable before reversing, but that's a work around to bad design, not a real solution. This is especially confusing when a number of other array methods (mostly those added with ES6) return new arrays with the altered content.
let arr = [1,2,3];
arr.map(x => x + 1);
console.log(arr); //Prints [ 1, 2, 3 ]
So what can we do about this? Javascript isn't know for it's immutability after all. As it turns out, it doesn't take that long to write a basic immutable List class in Javascript.
class List {
constructor(value, tailList) {
const that = this;
const headValue = value;
const tailValue = tailList;
const sizeValue =
tailList
? tailList.size() + 1
: headValue
? 1
: 0;
//Privileged methods
this.head = () => headValue;
this.tail = () => tailValue;
this.size = () => sizeValue;
this.prepend = (v) => new List(v, that);
this.append = (v) => that.reverse().prepend(v, that).reverse();
this.reverse = () => {
let val = that;
let list = new List(val.head());
val = val.tail();
while (val) {
list = list.prepend(val.head(), val);
val = val.tail();
}
return list;
}
this.forEach = (func) => {
let val = that;
while (val) {
func(val.head());
val = val.tail();
}
}
this.map = (func) => {
let val = that;
let list;
while(val) {
!list
? list = new List(func(val.head()))
: list = list.prepend(func(val.head()), val);
val = val.tail();
}
return list.reverse();
}
this.filter = (func) => {
let val = that;
let list;
while (val) {
if (func(val.head())) {
!list
? list = new List(val.head())
: list = new List(val.head(), list)
}
val = val.tail()
}
return list.reverse();
}
this.reduce = (func, zero = null) => {
let val = that;
let reducedValue = zero;
while (val) {
reducedValue = func(reducedValue, val.head());
val = val.tail();
}
return reducedValue;
}
}
//Public methods
toArray() {
let arr = [];
this.forEach(v => arr.push(v));
return arr;
}
reduceRight(func, zero) {
return this.reverse().reduce(func, zero);
}
//Static methods
static of(values) {
let list;
if (!values) {
list = new List();
} else if (values.constructor === Array) {
values.forEach((v) => !list ? list = new List(v) : list = list.prepend(v));
} else if (values.constructor === List) {
return values;
} else {
list = new List(values);
}
return list.reverse();
}
}
With this List object we have much of the same functionality as a Javascript Array, save for any mutating methods. "But Devin," you cry, "There is clearly an append and a prepend method, how is this not mutable? Do those not mutate the internal structure?"
An astute observation, to be sure. Indeed, those two methods do exist, but let's look at what they actually do:
this.prepend = (v) => new List(v, that);
this.append = (v) => that.reverse().prepend(v, that).reverse();
We'll start with prepend, as append is written in terms for prepend. The most notable thing is that prepend isn't actually changing state, it's instead creating an entirely new List object and returning that. Before we go any further, let's look at the actual structure of the List class.
class List {
constructor(value, tailList) {
//Privileged methods
this.head = () => {...};
this.tail = () => {...};
this.size = () => {...};
this.prepend = (v) => {...};
this.append = (v) => {...};
this.reverse = () => {...}
this.forEach = (func) => {...}
this.map = (func) => {...}
this.filter = (func) => {...}
this.reduce = (func, zero = null) => {...}
}
//Public methods
toArray() {...}
reduceRight(func, zero) {...}
//Static methods
static of(values) {...}
}
The important part to note here is the constructor as it betrays the actual intention of this class: to function as a single node in a larger string of singly linked nodes. The constructor takes in a "head" and a "tail", hides them as private variables (consts of course, we want to be fully immutable after all!), and builds privileged methods to give them access. The "head" variable is the value of the node, and the "tail" is the next node in the chain. A composed List would look something like this:
{1} -> {2} -> {3}
So knowing this let's go back to prepend. prepend takes in a value, the head, and creates a new node in the chain. The node becomes the first node with it's tail being the link to the previous first node. If we were to add 0 to our last example, it would return a list that looked like this:
{0} -> {1} -> {2} -> {3}
Knowing now how prepend works, let's look at append. Our append method reverses our list, prepends the value we want to add to the end, then reverse the list a second time. In action we would see this if we wanted to append 4:
{0} -> {1} -> {2} -> {3} //initial state
{3} -> {2} -> {1} -> {0} //reverse
{4} -> {3} -> {2} -> {1} -> {0} //prepend 4
{0} -> {1} -> {2} -> {3} -> {4} //reverse
"Why not just add it to the end instead of wasting resources reversing the array twice?" you might ask. And that's a fair question. Let's say we did want to do that, the immediate problem we would have is that it requires mutating the internal state of at the very least the final node in the array, as we have to give it a tail. This immediately breaks out immutability! In actuality we would have to change the state of EVERY node, because each note also knows how long it's chain is starting with it.
So what does this immutable list actually do for us? Let's look at the earlier example:
const printReverseArray = (a) => console.log(a.reverse().toArray());
const printArray = (a) => console.log(a.toArray());
let arr = List.of([ 1, 2, 3, 4, 5 ]);
printReverseArray(arr); //Prints [ 5, 4, 3, 2, 1 ], yay!
printArray(arr); //Prints [ 1, 2, 3, 4, 5 ], yay!
Because the state of arr can never change, List.reverse() gives us an entirely new List to work this. This is true for ALL of the methods that could mutate List, making it safe to work with when passing it around blind!
Immutability is a wonderful tool that creates safe, reusable objects leading to better and safer code. There are a number of wonderful immutable Javascript libraries out, my personal favorite being Facebook's Immutable.js, though I also highly recommend implementing various collections for yourself so you can see how they function.
About the author
Photo by Kaley Dykstra on Unsplash
Edit: Thanks to mbed67 (who also has their own blog) for pointing out that in the second code block I had incorrectly reported the result of the console log! This is now fixed, sorry for the confusion!