I prefer using Array.prototype.map over Array.prototype.forEach because .map semantically
signals to everyone that it constructs a new array, while .forEach might modify the existing one.
In order to actually prevent modifying the array in .map, one needs to use an immutable
array, see Avoiding Side Effects blog post. In this blog post I will
show another benefit of using an immutable list in my JavaScript programs - easy implementation
of Undo command.
This is an exploration in progress of immutable data in JavaScript. I am not sure that this example clearly shows the advantages of immutability. Consider this a practice exercise. I implement a Todo list using the traditional object oriented encapsulation and the same features using an immutable data structure. I also answered a few questions at the end of this blog post; these questions poped up as I was working with immutable objects.
Todo list using OO
I will start with implementing a simple Todo list using a regular array. Each item has a label and
done property.
Using individual todo items
My initial implementation allows to directly modify the state of a todo item in the collection
1 | function Todos() { |
The above code makes marking an individual item as done very convenient
// typical use
var todos = Todos();
var doFoo = todos.add('foo');
var doBar = todos.add('bar');
console.log(todos.toString());
// foo
// bar
doFoo.done = true;
console.log(todos.toString());
// foo done
// bar
doBar.done = true;
console.log(todos.toString());
// foo done
// bar done
Unfortunately I do not see how to implement todos.undo() if the list has no idea what has happened.
I will need to move done into the todos object
Using Todos API to mark item done
function Todos() {
var _todos = [];
var todosModule = {
add: function (label) {
_todos.push({
label: label,
done: false
});
return todosModule;
},
done: function (index) {
_todos[index].done = true;
return todosModule;
},
toString: function () {
return _todos.map(function (todo) {
return todo.label + ' ' + (todo.done ? 'done' : '');
}).join('\n');
}
};
return todosModule;
}
The Todos object only has 3 methods add, done and toString. One can easily add tasks,
print them, and mark an individual task as done.
var todos = Todos();
todos
.add('foo')
.add('bar');
console.log(todos.toString());
// foo
// bar
todos.done(0);
console.log(todos.toString());
// foo done
// bar
todos.done(1);
console.log(todos.toString());
// foo done
// bar done
There is only a single reference todos always pointing at the same object. When we call todos.add we modify
the only instance. This makes implementing undo simple.
clearDone
If we mark items done, let us clear the list of done items too.
clearDone: function () {
_todos = _todos.filter(function (todo) {
return !todo.done;
});
return todosModule;
}
// use clearDone
var todos = Todos();
todos.add('foo').add('bar');
todos.done(0);
console.log(todos.toString());
// foo done
// bar
todos.clearDone();
console.log(todos.toString());
// bar
Undo clearDone command
We will keep track of done calls using list of commands. Each command is an object that can reverse a
previous todos list modification. An example of a command with undo:
var sum = 0;
function add(a) {
sum += a;
return {
undo: function () {
sum -= a;
}
};
}
var undoAdd10 = add(10); // sum = 10
var undoAdd20 = add(20); // sum = 30
undoAdd20.undo(); // sum = 10
undoAdd10.undo(); // sum = 0
We should respect the action order, thus we will use a stack to keep list of commands to undo them in reverse order.
function Todos() {
var _todos = [];
var _commands = [];
var todosModule = {
add: function (label) {
_todos.push({
label: label,
done: false
});
return todosModule;
},
done: function (index) {
_todos[index].done = true;
return todosModule;
},
toString: function () {
return _todos.map(function (todo) {
return todo.label + ' ' + (todo.done ? 'done' : '');
}).join('\n');
},
clearDone: function () {
_commands.push({
// save entire list using undo function closure
undo: function (prevTodos) {
_todos = prevTodos;
}.bind(null, _todos)
});
_todos = _todos.filter(function (todo) {
return !todo.done;
});
return todosModule;
},
undo: function () {
if (_commands.length) {
_commands.pop().undo();
}
}
};
return todosModule;
}
we can set done, clear done tasks, then undo the clear operation
var todos = Todos();
todos.add('foo').add('bar');
todos.done(0);
// foo done
// bar
todos.clearDone();
// bar
todos.undo();
// foo done
// bar
Notice the added complexity that now is inside the Todos object. Because the undo commands need full access
to the list, the undo functionality is added inside the Todos closure.
Undo any action
Our undo clearDone feature just restores the previous list. Why don't we reuse it for other actions?
Let us factor it out into checkpoint function
function Todos() {
var _todos = [];
var _commands = [];
function checkPoint() {
_commands.push({
undo: function (prevTodos) {
_todos = prevTodos;
}.bind(null, _todos)
});
}
var todosModule = {
clearDone: function () {
checkPoint();
_todos = _todos.filter(function (todo) {
return !todo.done;
});
return todosModule;
}
// the rest is the same
}
}
Now we can just call checkPoint before any action, and we get the undo feature.
var todosModule = {
add: function (label) {
checkPoint();
_todos.push({
label: label,
done: false
});
return todosModule;
},
done: function (index) {
checkPoint();
_todos[index].done = true;
return todosModule;
},
clearDone: function () {
checkPoint();
_todos = _todos.filter(function (todo) {
return !todo.done;
});
return todosModule;
},
toString: function () {
return _todos.map(function (todo) {
return todo.label + ' ' + (todo.done ? 'done' : '');
}).join('\n');
},
undo: function () {
if (_commands.length) {
_commands.pop().undo();
}
}
};
Wait, something is wrong!
We are not correctly restoring the todo list after marking an item done
var todos = Todos();
todos.add('foo').add('bar');
todos.done(0);
console.log(todos.toString());
// foo done
// bar
console.log('undo done()');
todos.undo();
console.log(todos.toString());
// foo done
// bar done
Notice that the item foo still remains done! This is because we are making a copy of the
reference to the list, not a deep copy of the todos.
Deep clone _todos
A good approach to simplify the saving and restoring of todos list is to deep clone the list.
function checkPoint() {
var _ = require('lodash');
_commands.push({
undo: function (prevTodos) {
_todos = prevTodos;
}.bind(null, _.cloneDeep(_todos))
});
}
Now any operation can be undone, not matter how it is implemented
var todos = Todos();
todos.add('foo').add('bar');
todos.done(0);
console.log(todos.toString());
// foo done
// bar
console.log('undo done()');
todos.undo();
console.log(todos.toString());
// foo
// bar
I call this approach semi-immutable. We are making a copy of the internal data structure, with this extra complexity inside the Todos instance.
Multiple references and equality
If we reference the todos list in several places, can we check if it has been modified? For example, we could maintain the reference to the list in our MVC model object, and pass reference to the view object.
// model
var todos = Todos();
view.render(todos);
// view renders todos, allows user to mark items done
// should we save todos to the server?
To see if we need to save todos to the server, we could add new feature to the Todos object. Every
method that modifies the internal state could mark the object dirty.
function Todos() {
var _todos = [];
var _commands = [];
var _dirty;
var todosModule = {
add: function (label) {
checkPoint();
_dirty = true;
// ...
},
done: function (index) {
checkPoint();
_dirty = true;
// ...
},
clearDone: function () {
checkPoint();
_dirty = true;
...
}
undo: function () {
if (_commands.length) {
_commands.pop().undo();
_dirty = true;
}
},
isDirty: function () {
return _dirty;
}
};
Notice the added complexity: our list of todo items now has two additional features mixed in: undo commands and dirty state bit.
The dirty bit is also inefficient.
var todos = Todos():
save(todos);
todos.add('bar');
todos.undo();
if (todos.isDirty()) {
save(todos);
}
The second save is unnecessary, since we reverted the state back to the way it was during the first one.
Instead of the dirty bit, we could actually compare item contents for equality. For this we need to break privacy
and return _todos so that it is possible to compare two lists using deep equality comparison
lodash.isEqual.
function Todos() {
var _todos = [];
var _commands = [];
// no dirty bit
var todosModule = {
items: function()
isEqual: function (t) {
var _ = require('lodash');
return _.isEqual(t.items(), _todos);
}
}
}
We are both breaking the privacy and use expensive method just to confirm that nothing has changed since last time we used the object.
Immutable todo list implementation
The main principle behind the immutable data is that every time something changes we construct a new object. Instead of plain array, I will use a wrapper from seamless-immutable.
var Immutable = require('seamless-immutable');
function Todos(todos) {
todos = todos || Immutable([]);
var todosModule = {
add: function (label) {
var newTodo = {
label: label,
done: false
};
var added = todos.concat(newTodo);
// return new object
return Todos(added);
},
done: function (index) {
var changed = todos.map(function (todo, k) {
return k === index ? {
label: todo.label,
done: true
} : todo;
});
// return new object
return Todos(changed);
},
toString: function () {
return todos.map(function (todo, k) {
return k + ': ' + todo.label + ' ' + (todo.done ? 'done' : '');
}).join('\n');
}
};
return todosModule;
}
Notice how adding new todo item method changed:
// mutable
function Todos() {
var _todos = [];
var todosModule = {
add: function (label) {
_todos.push({
label: label,
done: false
});
return todosModule;
}
};
return todosModule;
}
// immutable
function Todos(todos) {
todos = todos || Immutable([]);
var todosModule = {
add: function (label) {
var newTodo = {
label: label,
done: false
};
var added = todos.concat(newTodo);
return Todos(added);
}
};
return todosModule;
}
We construct new added list by concatenating the existing immutable list with new item,
and then call Todos(added) to return completely new object. Each time we call a method on
the Todos object, we get back a reference to different object.
var todos = Todos();
var addedFoo = todos.add('foo');
var addedBar = addedFoo.add('bar');
todos === addedFoo; // false
todos === addedBar; // false
addedFoo === addedBar; // false
We need to be careful when using the object because we want to print the object after all modifications
var todos = Todos();
var addedFoo = todos.add('foo');
var addedBar = addedFoo.add('bar');
console.log(todos.toString()); // prints nothing - todos is empty
console.log(addedBar.toString());
// 0: foo done
// 1: bar
Another observation: when setting done property on an object we are constructing
new object, thus preventing any modifications through any other possible reference.
Undo command around immutable object
Because each operation on Todos returns new object, we could easily implement the Undo feature using an external proxy object.
function TodosWithUndo() {
var states = [Todos()];
var t = {
add: function (label) {
states.push(states[states.length - 1].add(label));
return t;
},
done: function (index) {
states.push(states[states.length - 1].done(index));
return t;
},
undo: function () {
if (states.length > 1) {
states.pop();
}
return t;
},
toString: function () {
return states[states.length - 1].toString();
}
};
return t;
}
The TodosWithUndo saves the reference to the current immutable
Use:
var ts = TodosWithUndo();
// ts is mutable
ts.add('foo').add('bar');
console.log('after done first');
ts.done(0);
// prints
// 0: foo done
// 1: bar
console.log(ts.toString());
ts.undo();
console.log(ts.toString());
// prints
// 0: foo
// 1: bar
In this implementation, we are sure that every operation creates a new Todo instance, completely separate from the previous one. Nothing in the application logic can modify the list of instances we keep inside TodosWithUndo - not even a stray reference returned to the outside can modify it! The reasoning about program's state and data flow becomes very simple.
Additional questions
Does an object added to the immutable list become immutable?
You can still modify the object via its original reference, but the object inside an immutable collection is a separate copy
'use strict';
var obj = {
foo: 'foo',
bar: 'bar'
};
var Immutable = require('seamless-immutable');
var list = Immutable([]).concat(obj);
console.log(list);
// [ { foo: 'foo', bar: 'bar' } ]
obj.foo = 'not foo';
console.log(list);
// [ { foo: 'foo', bar: 'bar' } ]
console.log('object itself', obj);
// object itself { foo: 'not foo', bar: 'bar' }
Is this a deep copy of an object?
Yes, the object is deep cloned when added to the immutable collection
'use strict';
var obj = {
foo: 'foo',
bar: {
baz: 'baz'
}
};
var Immutable = require('seamless-immutable');
var list = Immutable([]).concat(obj);
console.log(list);
// [ { foo: 'foo', bar: { baz: 'baz' } } ]
obj.bar.baz = 'not baz';
console.log(list);
// [ { foo: 'foo', bar: { baz: 'baz' } } ]
console.log('object itself', obj);
// object itself object itself { foo: 'foo', bar: { baz: 'not baz' } }
Can immutable data structures be used with 3rd party functional libraries, like lodash?
Almost. Lodash can take immutable data structures as inputs for methods that do not modify the input data structure: map, filter, etc. The returned object is NOT an immutable
var _ = require('lodash');
var list = Immutable([1, 2, 3]);
function double(x) { return x * 2; }
var doubled = list.map(double);
console.log(doubled);
// [2, 4, 6]
// doubled[1] = 10; // exception because doubled is Immutable
var _doubled = _.map(list, double);
console.log(_doubled);
// [2, 4, 6]
_doubled[1] = 10; // works because _doubled is a regular Array
A work around is to wrap the returned value in Immutable again
var _doubled = Immutable(_.map(list, double));
// _doubled is Immutable
A convenient library to work with Immutable is Ramda. Just pipe the result through Immutable function call
var R = require('ramda');
var _doubled = R.pipe(R.map(double), Immutable)(list);
console.log(_doubled);
// [2, 4, 6]
// _doubled is immutable too
Are there good libraries for working with immutable data and have large API?
I used seamless-immutable in the above example. It is very simple to use: just wrap an existing object or array to start. Other libraries have richer APIs. Take a look at mori and Immutable.
Isn't deep copy on each operation a slow and memory hungry process?
Yes, if we naively deep cloned everything. Luckily, people have programed the persistent data structures to store diffs efficiently. See this video by David Nolen @swannodette that explains mori implementation performance shortcuts.
Conclusions
Keeping some data immutable (Todos) helped clarify the data flow in this case. At the same time, other pieces can still mutate the state (TodosWithUndo). This way I could dip my toes into the immutable programming paradigm, without rewriting my entire application.