How Immutable Data Structures is Optimised?

Introduction

According to Wikipedia, in computing, a persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead, always yield a new updated structure. The term was introduced in Driscoll, Sarnak, Sleator and Tarjans‘ 1986 article.

But it sounds heavy right? Don’t worry we’ll try to understand it in very simple words. A mutable object is an object whose state can be modified or changed after it is created. An immutable object as the name suggests is an object whose state can’t be changed or modified after it is created. Examples of immutable data structures in JavaScript are numbers and strings. Examples of mutable data structures in JavaScript are objects, arrays, functions, classes, sets and maps.

let a = {
    show: 'Hello'
};

let b = a;

a.show = 'There';

console.log(b.show); // There
console.log(a.show); //There
console.log(a === b) // true

But the one thing to note in the above is you have made changes in the as a.show=’there’ but it is also reflecting the same changes in b.show also. The reason behind this is very simple in JavaScript when you did b=a. It does not mean it created a new object b which is storing the copy. But it means now b is containing the reference of a. That’s why b is also pointing to the same object which is already pointing and the changes made to the are also visible in b.

If we talk about the same scenario in the JavaScript then let’s discuss it with another example.

a=['Hello','There']
b=a;
a[0]="Bye";
console.log(a);		//['Bye', 'There']
console.log(b);	//['Bye', 'There']

Look here also in the case of array we have made changes to the elements present in the array ‘a’ but ultimately same changes are also reflecting in the ‘b’. Okay now we are clear about this as it’s because of the reference but what if we actually want to create copy of ‘a’ into ‘b’ so that if someone made any changes to ‘a’ should only be limited to ‘a ‘. Well for that we have to introduce a new operator in JavaScript i.e. known as Spread Operator.

Spread Operator (…)

The spread operator is very handy and we can also say is a quick syntax for adding items to arrays or basically combining arrays or objects, and spreading an array out into a function’s arguments. Didn’t get right? I too didn’t get the definition until I see couple of examples on that so let’s see what does it mean?

Let’s take above example and instead of doing b=a let’s do b=[…a].

a=['Hello','There']
b=[…a];
a[0]="Bye";
console.log(a);		//['Bye', 'There']
console.log(b);	//['Hello', 'There']

Now you can see that now instead of printing the same for array ‘a’ and ‘b’. It is showing the changes we made to the array ‘a’ only. But how it does it pulls all the elements present in the array ‘a’ one by one and puts it in the ‘b’. So basically what spread operator (…) is doing, it’s just making a copy of the a now b is not pointing to the same object instead it’s creating its own new copy. That’s why changes we made to array ‘a’ are limited to the ‘a’ itself.

But you must be thinking that is it the only thing we can do with (…) Spread Operator. No there are lot of things you can do such as:

• Copying an array
• Concatenating or combining arrays
• Using Math functions
• Using an array as arguments
• Adding an item to a list
• Adding to state in React
• Combining objects
• Converting NodeList to an array

Yes we got to know what Immutable Data Structures are and how it’s working in JavaScript but the biggest question is still in the mind which is:

What is the need for immutable data structures in JavaScript?

But before we are able to understand the need for immutable data structures, we have to know about Functional Programming. What is it and how immutable data structures are related to it?

Functional Programming if you want to understand in simple words is a programming paradigm or basically where you mostly construct and structure your code using functions.

• There is no mutation nor the shared state is allowed, as functions should always remain pure and true to their expression under this paradigm. It is also declarative rather than imperative/procedural. 
• We can say that Functional Programming was simply a bunch of functions in which outside scope nor mutation of objects isn’t allowed.

If you want to know more about functional programming in detail then you can read here 9 Functional Programming concepts to follow.

Let’s try to understand the concept of immutable data structure in Functional Programming.

First, understand the aspect of immutability and one without it in the physical world. A very important thing that gets ignored in the mutable/immutable debate is that of a “shared state”.

I’m worried that this thing is called a “functional programming thing” when it should be a “programming thing”.

We will also see the problems which are due to the mutability state, and demonstrate that those problems are things you find in the programming world a LOT. There are lots of things from entire books, best practices, design patterns, frameworks, libraries,  tools, platforms, consultants, companies, etc. designed to solve those problems.

In the natural world, nothing changes without communication. Suppose that If I need to pay you $10 from my bank account in the old one paper-book-based banking system, how does the transaction take place?

• Suppose if I go to the bank and tell the bank that I wish to give you $10.
• For expressing that transaction The bank also writes an additional row in their ledger.
• The bank further tells you, or your bank that you may withdraw $10.

The same transaction in a mutable program with three “objects” representing you, me and the bank operates like this:

Then it is quite obvious that all three of us must have access so that we can see the sheet of paper that stores our balances.

What I do, I just go to the sheet of paper and subtract $10 from my bank balance, erase the original sum, and replace it with one that was lower by $10. I at the same find YOUR bank balance, add $10 to it, and then delete/erase the old value and change it with the new one.

This is called a “mutable shared state”. A shared state is fine if it is immutable. The one very important thing about Mutable state that it is fine if it is not shared.

Now the thing to think is of What if more than one person is doing changes such as adding or subtracting values? Of yeah – locking!

Consider that thousand accounts on that sheet of paper?

What if the person who has the lock dies due to some unforeseen circumstances? Oh yeah – “locking with timeouts”, “journaling”.

What if someone modifies rows they shouldn’t? Auditing of access. Code reviews of the code. Compliance measures.

What is the case if I ever wanted to know about the details of all transactions made so far? “Third-party history/journalling system”

Well this service now has important data. “Cool – more products to protect that service! More jobs!”

What if that sheet of paper remains of no used because of all the erasing/rewriting? “Scribes to periodically copy that sheet onto different stand-by sheets.” “A factory pattern to create the sheet in the first place” “A singleton pattern to ensure access to the same sheet.

When you use mutable values then you’ll notice these problems are not obvious.

In systems with immutable state, the state transitions take place from the “one legit/genuine state” into the “next legit/genuine state” by communicating and agreeing on what the next state is. The which comes in the mutable state must be clever though beforehand, are obvious and stick out like a sore thumb in the immutable state. “What happens if communication doesn’t go through?”

You are supposed to handle these situations very well. You can also say from the above scenario that Transaction history is a byproduct of the working of mutation. Good thing is that there is no “locking” or any other problem.

I know this was a hell of a lot of English, but it was necessary to solve the given problem. I hope now you have a clear idea of how immutable data structure is effecting Functional Programming.

But the main topic of the blog was the optimisation of these immutable data structures, So let’s see how can we achieve it?

How to Optimise the Immutable Data Structures?

We can optimise the immutable data structures by using Tries because also known as prefix tree. In basic terms, we can say that it is a data structure that is used for locating specific keys within a set. Often these keys are strings associated with the links between nodes. For accessing the element in the tries, you would have to first access it recursively using Depth-Fist-Search (DFS).

One thing that makes it differentiable from the other data structures as a tree (Binary Search Tree) is that all children node have a common prefix with the parent node.

How the tries are helpful in optimisation of immutable data structure is that suppose if you want to create a  new array then it would take O(n) time right? But as you can see in tries there’s branching so the complexity for input could be done in O(log(branch_factor)). And if you have ever studied the tries before then you must have known that branch-factor is constant O(logn).

Frequently Asked Questions

Conclusion

From the above article we get to know the importance of immutable data structure, how are they different from the mutable data structures and even discussed the real-life scenario with it. And we also get to know as for the implementation part immutable data structure can be optimised with the help of tries but didn’t discuss the implementation for the same otherwise it would be lengthy.

And if you want to learn how you can implement the tries data structures then you can learn from here Using Trie in Data Structures. If you’re not fond of a blog/documentation then you can also watch the video here Learn Tries for competitive programming for free.

By Yogesh Kumar