hamt's Introduction

hamt

For the old any-based API, refer to the main branch.

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/v2

Documentation

GoDoc

Technical notes

The implementation canonicalizes tree structures of HAMTs by eliminating intermediate nodes during delete operations as described in the CHAMP paper.

References

License

The Unlicense

hamt's People

Contributors

Stargazers

Watchers

hamt's Issues

Imperative methods

Problem

We currently use a functional style for all the interfaces of persistent data structures.
- This is primarily the easiness of writing programs in a functional style.
We implicitly use option types and take references of keys and values through pointer references in methods of persistent data structures.
It's not optimal for performance.
- e.g. We can't know if entries are inserted/removed or not at the same time!
- Go is primarily a system programming language but not a functional programming language!
The interface will be inconsistent with methods providing destructive updates, which might be implemented in the future.
- e.g. HashMap::insert() | im

Examples

func (m Map[K, V]) Find(k K) *V {
  ...
}

func (m Map[K, V]) Insert(k K, v V) Map[K, V] {
  ...
}

Solution

Migrate to imperative interfaces of persistent data structures.
- An implementation is in #25.

Examples

func (m Map[K, V]) Find(k K) (V, bool) {
  ...
}

func (m Map[K, V]) Insert(k K, v V) (Map[K, V], bool) {
  ...
}

References

The original discussion is in #16.
im, which is probably the most popular persistent data structure library in Rust adopts imperative interfaces for their implementations.
- I guess it's because Rust users usually care more about performance than easiness in programming.

raviqqe / hamt Goto Github PK

hamt's Introduction

hamt

Installation

Documentation

Technical notes

References

License

hamt's People

Contributors

Stargazers

Watchers

Forkers

hamt's Issues

Problem

Examples

Solution

Examples

References

Recommend Projects

Recommend Topics

Recommend Org