What libraries provide persistent data structures?

Question

I've become addicted to Clojure's core data structures. When working in other languages, I try to stay true to their respective idioms, but occasionally, a few persistent data structures are exactly the right solution to the problem.

In particular, I'm looking for implementations of Phil Bagwell's vectors and array mapped tries (ie hash maps). Relevant libraries should include sets, queues, and sorted set/map variants for bonus points.

Answer 1

• Python: https://github.com/halgari/clojure-py
• Haskell's HAMT library: http://hackage.haskell.org/package/unordered-containers
• Java: https://pcollections.org/
• C#: http://www.itu.dk/research/c5/
• JavaScript: https://github.com/isaacbw/immutable-collections/

Haskell has a lot of persistent collections in various libraries, enough that it would be unseemly to list them here so I only mentioned the closest equivalent to Clojure's HAMTs.

I would like to see a 32-ary variation on unordered-containers that is more like Clojure though.

Answer 2

This one is part of my own library but I think I have to mention it because it is IMHO unique and very useful: PersistentTreeGrid. It offers:

• A true persistent data structure
• Stores data in indexed 3D space
• Sparse storage - blocks of identical values get coalesced, so you can have huge areas with the same value with significantly reduced storage needs.
• Subdivision is implemented via a 64-way tree of 4x4x4 grids
• Various fast iteration strategies for scanning and modifying areas in space

It's fast enough to be used as the backing store for games (e.g. sparse storage of deformable 3D terrain).

It's written in Java, but I've used it successfully from other JVM languages.

Answer 3

• Clojure: http://clojure.org/data_structures
• Scala: http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html
• Ruby: https://github.com/hamstergem/hamster
• JavaScript: https://github.com/swannodette/mori
• Java: http://pcollections.org/

Answer 4

For Python there is a library called pyrsistent (I'm the author). It focuses solely on persistent/functional data structures.

It contains implementations of persistent vector, map, set, record, bag, list, dequeue as well as type and invariant checked versions of the vector, map and set.

There are also a bunch of convenience functions for converting to/from the built in counterparts.

See the github page for more information and examples.