Immutable and Memory-Efficient Maps and Sets in Go
Immutable and Memory Efficient Maps and Sets in Go.
hamtprovides immutable collection types of maps (associative arrays) and sets implemented as Hash-Array Mapped Tries (HAMTs). All operations of the collections, such as insert and delete, are immutable and create new ones keeping original ones unmodified.
Hash-Array Mapped Trie (HAMT) is a data structure popular as a map (a.k.a. associative array or dictionary) or set. Its immutable variant is adopted widely by functional programming languages like Scala and Clojure to implement immutable and memory-efficient associative arrays and sets.
go get github.com/raviqqe/hamt
The implementation canonicalizes tree structures of HAMTs by eliminating intermediate nodes during delete operations as described in the CHAMP paper.