?

Log in

No account? Create an account
Somehow I'd thought that immutable data structure libraries for… - Notes from a Medium-Sized Island [entries|archive|friends|userinfo]
Jason

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

[Jul. 20th, 2015|08:18 am]
Jason
[Tags|]

Somehow I'd thought that immutable data structure libraries for javascript like immutable.js and mori actually hashed data structure constants so that a sound and complete equality check (assuming no hash collisions) was O(1). And yet:
// immutable.js
function deep(n) {
  var x = Immutable.List([n]);
  for(var i = 0; i < 10000; i++) {
    x = Immutable.List([x]);
  } return x;
}
var x = deep(2);
var y = deep(2);

console.log(x === y); // → false
console.log(x.equals(y)); // → Uncaught RangeError: Maximum call stack size exceeded

// mori.js
function deep(n) {
  var x = mori.list(n);
  for(var i = 0; i < 10000; i++) {
    x = mori.list(x);
  } return x;
}
var x = deep(2);
var y = deep(2);

console.log(x === y); // → false
console.log(mori.equals(x,y)); // → Uncaught RangeError: Maximum call stack size exceeded

I guess it's too expensive to do that in practice?
LinkReply