Capsule - The Capsule Hash Trie Collections Library

•    Java

---

Capsule aims to become a full-fledged (immutable) collections library for Java 8+ that is solely built around persistent tries. The library is designed for standalone use and for being embedded in domain-specific languages. Capsule still has to undergo some incubation before it can ship as a well-rounded collection library. Nevertheless, the code is stable and performance is solid.

hashmap trie immutable immutable-collections persistent-data-structure hashset performance data-structure collections map list champ

rpds - Rust Persistent Data Structures

•    Rust

---

Rust Persistent Data Structures provides fully persistent data structures with structural sharing. Your classic functional list.

data-structures persistent-data-structure immutable-data-structures data-structure

immutable - Thread-safe, persistent, immutable collections for the Crystal language

•    Crystal

---

Efficient, thread-safe immutable data structures for Crystal. Whenever an Immutable data structure is "modified", the original remains unchanged and a modified copy is returned. However, the copy is efficient due to structural sharing. This makes Immutable data structures inherently thread-safe, garbage collector friendly and performant.

crystal immutable-collections vector hash data-structures functional-programming persistent-data-structure

Forest - A collection of persistent immutable trees.

•    Swift

---

A minimalist implementation of a binary tree using indirect enum. Forest contains a benchmarks app.

persistent-data-structure binary-trees

persistent-merkle-tree

•    TypeScript

---

A binary merkle tree implemented as a persistent data structure. When dealing with large datasets, it is very expensive to merkleize them in their entirety. In cases where large datasets are remerkleized often between updates and additions, using ephemeral structures for intermediate hashes results in significant duplicated work, as many intermediate hashes will be recomputed and thrown away on each merkleization. In these cases, maintaining structures for the entire tree, intermediate nodes included, can mitigate these issues and allow for additional usecases (eg: proof generation). This implementation also uses the known immutability of nodes to share data between common subtrees across different versions of the data.

typescript persistent-data-structure sha256 merkle-tree hash ethereum merkle tree

treap - A thread-safe, persistent Treap (tree + heap) for ordered key-value mapping and priority sorting

•    Go

---

Tread-safe, persistent treaps in pure Go. Treap is tested using go 1.14 and later, but is likely to work with earlier versions.

tree threadsafe concurrency persistent persistent-data-structure concurrent heap datastructure treap

persistent - Persistent data structure in Go

•    

---

Persistent data structure in Go

vector data-structures hashmap persistent-data-structure

immutable-tuple - Immutable finite list objects with constant-time equality testing (===) and no memory leaks

•    Javascript

---

Immutable finite list objects with constant-time equality testing (===) and no memory leaks. Although the tuple function can be invoked using new tuple(...) syntax, using new is not recommended, since the new object will simply be thrown away.

memoization immutable functional functional-programming tuples equality persistent immutability garbage-collection persistent-data-structure internalization memory-leak tuple equality-test sequence data data-structure intern interned internalized deep-equality weakmap