Thursday, July 31, 2014

Hierarchical persistent data structures in javascript (using underscore.js)

Lately, I have been studying a lot about functional programming, and things like LISP, Clojure, Scala but since mostly I program in Javascript and python, I also studied a lot the functional programming concepts in these 2 languages.

The problem

I have a model (using MVC pattern) and I want to keep both the initial model state, and the one that is changed afar some operations. I wanted initially to use something like cloning or deep copying but it seems just to waste memory, if for instance I change only one thing in a hierarchy, so I don't need everything clones.

The solution : persistent data structures

I knew that what I wanted is to use persistent data structures in javascript and although they are available in libraries such as immutable or mori, I needed one that is hierarchical.

Persistent data sturctures acording 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. (A persistent data structure is not a data structure committed to persistent storage, such as a disk; this is a different and unrelated sense of the word "persistent.")

Solution:


So I want something like:

  initial_state = {a:1, b:2};  
  modified_state = change(model,"a","abc"))   

where initial_state remains unchanged and modified_state is {a:"abc",b:2}. This is very simple using something like _.clone(initial_state) in underscore.js. But what if I want something like:

  initial_state = model = {l:[{id:1}, {id:2}], b:2};  
  modified_state = change(model,"l[1].id",3)  

resulting in: modified_state = {l:{id:1},{id:3}], b:2}. Here copy, deep copy or clone doesn't help. So what if I write a function like this:

 function change(obj,path,val)  
 {  
   var new_obj = _.clone(obj);  
   var path = path.replace("[",".").replace("]","");  
   var levels = path.split(".");  
   if(levels.length>1)  
   {  
     var head = _.first(levels)  
     var tail = path.replace(head+".","")  
     new_obj[head] = change(obj[head],tail,val)  
   }  
   else  
   {  
     new_obj[path] = val;  
   }  
   return new_obj;  
 }  

It works!

I can even do:

 initial_state = {g:  
     [  
       {id:1, values:[1,2,3]},  
       {id:2, values:[3,4]}  
     ],  
   b:2}  
 new_state1 = change(model,"g[1].values[1]",7);  
 new_state2=change(model,"g[1].values",[7,2]);