README
¶
hamt
Immutable and Memory Efficient Maps and Sets in Go.
This package hamt provides 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.
Installation
go get github.com/raviqqe/hamt
Documentation
Technical notes
The implementation canonicalizes tree structures of HAMTs by eliminating intermediate nodes during delete operations as described in the CHAMP paper.
References
License
Documentation
¶
Overview ¶
Package hamt provides 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.
Index ¶
- type Entry
- type Map
- func (m Map[K, V]) Delete(k K) Map[K, V]
- func (m Map[K, V]) Find(k K) *V
- func (m Map[K, V]) FirstRest() (*K, *V, Map[K, V])
- func (m Map[K, V]) ForEach(cb func(K, V) error) error
- func (m Map[K, V]) Include(k K) bool
- func (m Map[K, V]) Insert(k K, v V) Map[K, V]
- func (m Map[K, V]) Merge(n Map[K, V]) Map[K, V]
- func (m Map[K, V]) Size() int
- type Set
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Entry ¶
Entry represents an entry in a collection, which can be compared to values of type T (which is typically also the underlying type of the Entry).
type Map ¶
Map represents a map (associative array).
func (Map[K, V]) Find ¶
func (m Map[K, V]) Find(k K) *V
Find finds a value corresponding to a given key from a map. It returns nil if no value is found.
func (Map[K, V]) FirstRest ¶
FirstRest returns a key-value pair in a map and a rest of the map. This method is useful for iteration. The key and value would be nil if the map is empty.
func (Map[K, V]) Include ¶
Include returns true if a key-value pair corresponding with a given key is included in a map, or false otherwise.
type Set ¶
type Set[T Entry[T]] struct { // contains filtered or unexported fields }
Set represents a set.
func (Set[T]) FirstRest ¶
FirstRest returns a pointer to a value in a set and a rest of the set. This method is useful for iteration.
Source Files