This is a stable fork of; it will not introduce breaking changes.


Persistent data structures for Go. See the full package documentation

Install with

go get
Expand ▾ Collapse ▴



    Fully persistent data structures. A persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not update the structure in-place, but instead always yield a new structure.

    Persistent data structures typically share structure among themselves. This allows operations to avoid copying the entire data structure.



    This section is empty.


    This section is empty.


    This section is empty.


    type Any

    type Any interface{}

      Any is a shorthand for Go's verbose interface{} type.

      type List

      type List interface {
      	// IsNil returns true if the list is empty
      	IsNil() bool
      	// Cons returns a new list with val as the head
      	Cons(val Any) List
      	// Head returns the first element of the list;
      	// panics if the list is empty
      	Head() Any
      	// Tail returns a list with all elements except the head;
      	// panics if the list is empty
      	Tail() List
      	// Size returns the list's length.  This takes O(1) time.
      	Size() int
      	// ForEach executes a callback for each value in the list.
      	ForEach(f func(Any))
      	// Reverse returns a list whose elements are in the opposite order as
      	// the original list.
      	Reverse() List

        List is a persistent list of possibly heterogenous values.

        func NewList

        func NewList() List

          NewList returns a new, empty list. The result is a singly linked list implementation. All lists share an empty tail, so allocating empty lists is efficient in time and memory.

          type Map

          type Map interface {
          	// IsNil returns true if the Map is empty
          	IsNil() bool
          	// Set returns a new map in which key and value are associated.
          	// If the key didn't exist before, it's created; otherwise, the
          	// associated value is changed.
          	// This operation is O(log N) in the number of keys.
          	Set(key string, value Any) Map
          	// Delete returns a new map with the association for key, if any, removed.
          	// This operation is O(log N) in the number of keys.
          	Delete(key string) Map
          	// Lookup returns the value associated with a key, if any.  If the key
          	// exists, the second return value is true; otherwise, false.
          	// This operation is O(log N) in the number of keys.
          	Lookup(key string) (Any, bool)
          	// Size returns the number of key value pairs in the map.
          	// This takes O(1) time.
          	Size() int
          	// ForEach executes a callback on each key value pair in the map.
          	ForEach(f func(key string, val Any))
          	// Keys returns a slice with all keys in this map.
          	// This operation is O(N) in the number of keys.
          	Keys() []string
          	String() string

            A Map associates unique keys (type string) with values (type Any).

            func NewMap

            func NewMap() Map

              NewMap allocates a new, persistent map from strings to values of any type. This is currently implemented as a path-copying binary tree.

              Source Files