Immutable Hash and Array implementation in JavaScr

Question

Is there simple immutable hash and array implementation in javascript? I don't need best speed, a reasonable speed better than a clone would be good.

Also, if there are simple implementations in Java or some other languages that can be easily understood and ported to JavaScript, it would be also nice.

UPDATE:

The goal isn't to just froze the hash (or array), but to make an efficient implementation of update operation - update of immutable hash should return a new immutable hash. And it should be more efficient than doing it by "clone original and update it".

Native JS types have complexity of update something like O(1), with cloning the complexity will be O(n), with special immutable data structures (what I asked for) it will be 0(log(n))

UPDATE2: JavaScript already has Array / Hash :

Yes, but they are mutable, I need something similar but immutable, basically it can be done very simply by cloning hash2 = hash1.clone(); hash2[key] = value but it's very inefficient, there are algorithms that made it very efficient, without using the clone.

hash1 = {}
hash2 = hash1.set('key', 'value2')
hash3 = hash1.set('key', 'value3)

console.log(hash1) // => {}
console.log(hash2) // => {key: 'value2'}
console.log(hash3) // => {key: 'value3'}

SOLUTION:

It's not an implementation for immutable hash, but more like a hack for my current problem, maybe it also helps someone.

A little more about why I need immutable data structures - I use Node.js and sort of in-memory database. One request can read database, other update it - update can take a lot of time (calling remote services) - so I can't block all read processes and wait until update will be finished, also update may fail and database should be rolled back. So I need to somehow isolate (ACID) read and write operations to the in-memory database.

That's why I need immutable arrays and hashes - to implement sort of MVCC. But it seems there is a simpler way to do it. Instead of updating database directly - the update operation just records changes to database (but not perform it directly) - in form of "add 42 to array db.someArray".

In the end - the product of update operation will be an array of such change commands, and because it can be applied very quickly - we can block the database to apply it.

But, still it will be interesting to see if there are implementation of immutable data structures in javascript, so I'll leave this question open.

Answer 1

The only way to make an object immutable is to hide it inside a function. You can then use the function to return either the default hash or an updated version, but you can't actually store an immutable hash in the global scope.

function my_hash(delta) {
    var default = {mykey: myvalue};
    if (delta) {
        for (var key, value in delta) {
            if (default.hasOwnProperty(key)) default[key] = value;
        }
    }
    return default;
}

I don't think this is a good idea though.

Answer 2

The best way to clone an object in Javascript I'm aware of, is the one contained in underscore.js

Shortly:

_.clone = function(obj) {
  if (!_.isObject(obj)) return obj;
  return _.isArray(obj) ? obj.slice() : _.extend({}, obj);
};

_.extend = function(obj) {
  each(slice.call(arguments, 1), function(source) {
    for (var prop in source) {
      obj[prop] = source[prop];
    }
  });
  return obj;
};

Answer 3

I know this question is old but I thought people that were searching like me should be pointed to Facebook's Immutable.js which offers many different types of immutable data structures in a very efficient way.

Answer 4

I had the same requirements for persistent data structures for JS, so a while ago I made an implementation of a persistent map.. https://github.com/josef-jelinek/cofy/blob/master/lang/feat.js

It contains implementation of a balanced tree based (sorted) map, and a naive copy-on-write map (and unfinished persistent vector/array).

var map = FEAT.map();
var map1 = map.assoc('key', 'value');
var value = map1.get('key');
var map2 = map1.dissoc('key');
...

it supports other methods like count(), contains(key), keys(into = []), values(into = []), toObject(into = {}), toString()

The implementation is not too complicated and it is in public domain. I accept suggestions and contributors too :).

Update: you can find unit tests (examples of usage) at https://github.com/josef-jelinek/cofy/blob/master/tests/test-feat.html

Update 2: Persistent vector implementation is now there as well with the following operations: count(), get(i), set(i, value), push(value), pop(), toArray(into = []), toString()