9

I'm looking for a functional library with persistent data structures. I only need nested arrays and dictionaries. There are some functional javascript libraries, but they are not geared towards immutability. I want to be able to write

var dict = makeDictionary({
  'foo': 1;
  'bar': {
     'ely': 2;
  }
});
var newDict = dict.assoc('foo', 42).assoc('bar', 'tender', 30).dissoc('bar', 'ely');
assert.eq dict.bar.ely, 2; // unchanged
assert.eq newDict.bar.tender, 30; // added
assert.eq newDict.bar.ely, undefined; // removed

While underscore comes close in some cases, especially with arrays, it modifies dictionary arguments. I could also use clojurescript, but I'd prefer a more light-weight approach.

Community
  • 1
  • 1
Adam Schmideg
  • 10,590
  • 10
  • 53
  • 83
  • just to clarify (because I am currently working on something quite similar), do you need the resulting persistent map behave as a native object including "." access? That would require either simulating using getters, or copying the whole structure from the modification up and freezing it, which for big flat maps becomes inefficient quite quickly (and both require ES5)... or are you fine with functions/methods accessing the content (my approach)? – jJ' May 02 '12 at 20:43
  • I'd be happiest with the doc-access solution, seeing its drawbacks, though. I don't have huge maps anyway. The ES5 requirement... well, I'm going to think about your function-access approach. – Adam Schmideg May 03 '12 at 19:59
  • there is an alternative I added (to measure performance gains against naive approach). I added naive persistent map 'Nap' which does full copy-on-write. There are two variants of assoc/dissoc, but once you are done you get a native object (possibly frozen if ES5 is supported) you can access as usually. – jJ' May 04 '12 at 12:31

4 Answers4

9

I'd take a look at Mori. It packages up ClojureScript's functional data structure for use from plain old Javascript. Since the data structures are coming from ClojureScript I'd expect them to be better tested, more complete and more performant than other libraries.

https://github.com/swannodette/mori

Matt Wonlaw
  • 12,146
  • 5
  • 42
  • 44
3

I finalized my implementation of Persistent Map (and will finish Persistent Vector soon) for JavaScript, because there seems to be an increasing demand.

There are several specifics compared to e.g. Java (lack of equals, hashCode to rely on), so the implementation uses sorted balanced binary tree (balancing is actually simplified and sped up by immutability) and === for equality and < or custom function for lower-than.

the code of Feat.js (the project code name) is available at feat-sorted-map.js at github.com

You can see a page with working tests in action online at feat.js at cofylang.org

Currently, there is no documentation except the source code and tests, but I am working on finishing that as well.

Update: there is an implementation of a persistent vector available there as well, and the speed has been improved in orders of magnitude. (it has been cleaned-up as well) feat-vector.js at github.com

jJ'
  • 3,038
  • 32
  • 25
  • @jJ, what did you do to speed it up? – Scott Klarenbach Jun 21 '13 at 23:02
  • @Scott in my case I had to abandon Object.freeze, it is just unusable for its slowness (http://jsperf.com/object-freeze-performance). But other than that I used fixed-structure objects with monomorphic functions as much as possible, that is the biggest thing (for direct access, inlining etc.) IMHO. Profiler in developer tools is your best friend here. – jJ' Jul 02 '13 at 15:56
1

There's also:

https://github.com/hughfdjackson/immutable

Which is based on the persistent hash trie algorithm here:

https://github.com/hughfdjackson/persistent-hash-trie

Might be worth looking into.

The code for this is nicer imho, but my benchmarks show it's running nearly an order of magnitude slower than the one listed above.

Scott Klarenbach
  • 37,171
  • 15
  • 62
  • 91
1

The most popular and as far as I know the only one still under active development is https://immutable-js.com/

but if you want richer API then you can go with Mori as well but I'm not sure if it will be much more lightweight approach than using ClojureScript directly.

Arek C.
  • 1,271
  • 2
  • 9
  • 17