7

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.

Improve this question
10
  • 1
    What is "hash and array". JavaScript has arrays; are you thinking of an indexed collection something like java.util.Vector? Commented Nov 9, 2012 at 19:05
  • Every object in javascript can be thought of as a hashtable<K,V> where you can access the value of by saying obj[key] What exactly are you loking for? Commented Nov 9, 2012 at 19:07
  • Yes JavaScript has Arrays but they are mutable, I need something similar but immutable. Commented Nov 9, 2012 at 19:08
  • you need "an efficient implementation" but "not the best speed"..? Commented Nov 9, 2012 at 19:09
  • 1
    "efficient implementation" but "not the best speed? Yes, it should be two or five times slower than native mutable types, but not as terribly inefficient as by doing it with clone operation. Commented Nov 9, 2012 at 19:14

4 Answers 4

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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()

Improve this answer

Comments

0

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.

Improve this answer

4 Comments

Let me introduce you to Object.freeze() :P
@ŠimeVidas whoa, neat! I did not know about that.
Thanks, but the goal isn't to freeze an object but an efficient way to do slightly modified copies.
let me introduce you to Object.freeze() performance jsperf.com/object-freeze-performance I could not believe that at first.
0

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;
};
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.