CODEWITHSUNDEEP
data-structuresclojurelibrariesimmutability
Brandon Bloom
Brandon Bloom

Reputation: 1342

What libraries provide persistent data structures?

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.

Upvotes: 13

Views: 1844

Answers (6)

bitemyapp
bitemyapp

Reputation: 1647

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.

Upvotes: 10

GlenPeterson
GlenPeterson

Reputation: 5206

Paguro provides type-safe versions of Clojure's immutable collections and a few other tools to make functional programming in Java 8 a little easier. This Vector is faster than the one in PCollections. The entire project fits in a 200K jar file that is compiled in the compact1 profile. All collections are painstakingly fit into the standard Java Collections API. Five collection implementations from Clojure are included: Vector, HashSet, HashMap, SortedSet, and SortedMap.

There's an RRB-Tree in the works (Based on another Phil Bagwell paper) like Clojure's Vector, but supports inserts at any point.

Upvotes: 1

ducky
ducky

Reputation: 1113

For Python, there is fn.py which is implementing persistent data structures along with adding some other functional features.

There is another python library pyrsistent which looks more maintained and performant.

Upvotes: 1

Tobias Gustafsson
Tobias Gustafsson

Reputation: 297

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.

Upvotes: 2

Brandon Bloom
Brandon Bloom

Reputation: 1342

Upvotes: 2

mikera
mikera

Reputation: 106351

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.

Upvotes: 2

Related Questions