Persistent data structures,trie and immutable js

Persistent data structures,trie and immutable js

June 18, 2018

If you do not know about immutability read more here http://truetocode.com/understanding-concepts-of-immutables-and-mutables-in-javascript/378/.

Immutable data is never changed once it is created.It can prevent unwanted alteration of data and helps us in more efficient programming.Mutability may cause unwanted bugs as the data may get changed accidentally.

Consider we have an array that contains the name of fruits say,


Now consider that  for some reason we want to push the name of an Car into the array and do some thing with it.For that we call the pushCar method . After that  we want to  push the name of a fruit into the array and do some thing with it using the pushFruit method. In the push fruit method we expect the array to only contain fruits but our array has the name of a car since it was mutated.

See the below code to get better understanding


We can achieve our requirement using spread operator as the spread operator copies the parent a

But,when we have a large data set this is very expensive as spread operator copies the parent and copying is very expensive.

To tackle this problem and make the array of fruits not to change every time ,we need to use Persistent  data structures.A persistent data structure is a data structure that always keeps the previous version of itself when it is modified. There are a few libraries that lets us use persistant data structures like immutable.js by facebook and mori which is library for using ClojureScript’s persistent data structures.Now we look at the example using immutable.js

Here we can see that parent ‘a’ did’nt change as it is not mutated.

Now to understand what immutables js library does we have to understand what ‘Tries‘ are

Trie pronounced as ‘try’ is a tree like data strucuture in which the nodes of the tree has alphabet/strings which helps to traverse down the branches to get  to get the whole string.

Consider the following array

The above array is a representation of the below trie.The root of the trie is kept null.The trie represenation is used for representing dictionaries,phone book etc.


Now if we add ‘bfk’ in to the tree ,


We are not using string as the key in our case that is the array of fruits .instead we use the binary of the index as keys which gives us.The root node has index 0.Here the following example has indexing 0 for the first child but it is just for  providing an example

Now we  change the fruit in the an index.The orange colored lines show path.


As you can see the new array and parent shares structure,this is called structural sharing .Structural sharing is the one techniques used by immutable js to achieve immutabiliy.

This is just an overview.The examples given here are just for the purpose of giving you an idea on immutabiliy.There is a great talk by Anjana Vakil on the topic of immutables,watch it and don’t forget to read the documentations on immutablejs.Link to the references are given below



No Comments

Leave a Reply

Your email address will not be published. Required fields are marked *