README

go-immutable

Immutable map/set/list for go.

Benchmark

This library comes with benchmark test to compare against builtin types (there's no builtin set so that's only list and map). Here is an example of the benchmark result (with baseline is builtin):

$ go test -bench . -benchmem
goos: linux
goarch: amd64
pkg: go.yhsif.com/immutable
BenchmarkListBuilder/literal-10/baseline-4              1000000000               0.296 ns/op           0 B/op          0 allocs/op
BenchmarkListBuilder/literal-10/immutable-4              3684753               324 ns/op             544 B/op          5 allocs/op
BenchmarkListBuilder/10/baseline-4                      11090810               108 ns/op             160 B/op          1 allocs/op
BenchmarkListBuilder/10/immutable-4                      3189986               376 ns/op             544 B/op          5 allocs/op
BenchmarkListBuilder/1024/baseline-4                       78103             15251 ns/op           22528 B/op        769 allocs/op
BenchmarkListBuilder/1024/immutable-4                      55538             21656 ns/op           55360 B/op        773 allocs/op
BenchmarkListBuilder/131072/baseline-4                       436           2739739 ns/op         3143688 B/op     130817 allocs/op
BenchmarkListBuilder/131072/immutable-4                      162           7346655 ns/op         7338070 B/op     130821 allocs/op
BenchmarkListRange/10/baseline-4                        336276412                3.56 ns/op            0 B/op          0 allocs/op
BenchmarkListRange/10/immutable-4                       42435681                28.3 ns/op             0 B/op          0 allocs/op
BenchmarkListRange/1024/baseline-4                       3885120               309 ns/op               0 B/op          0 allocs/op
BenchmarkListRange/1024/immutable-4                       460292              2604 ns/op               0 B/op          0 allocs/op
BenchmarkListRange/131072/baseline-4                       30994             38736 ns/op               0 B/op          0 allocs/op
BenchmarkListRange/131072/immutable-4                       3529            336382 ns/op               0 B/op          0 allocs/op
BenchmarkMapBuilder/literal-5/baseline-4                 8661763               138 ns/op               0 B/op          0 allocs/op
BenchmarkMapBuilder/literal-5/immutable-4                1000000              1041 ns/op            1024 B/op          8 allocs/op
BenchmarkMapBuilder/10/baseline-4                        1497246               804 ns/op             582 B/op          1 allocs/op
BenchmarkMapBuilder/10/immutable-literal-4                358076              3321 ns/op            2770 B/op         11 allocs/op
BenchmarkMapBuilder/10/immutable-builder-4                556004              2175 ns/op            1852 B/op          8 allocs/op
BenchmarkMapBuilder/1024/baseline-4                         6931            170979 ns/op          178829 B/op       1566 allocs/op
BenchmarkMapBuilder/1024/immutable-literal-4                2346            513132 ns/op          512781 B/op       1634 allocs/op
BenchmarkMapBuilder/1024/immutable-builder-4                3469            351918 ns/op          345981 B/op       1602 allocs/op
BenchmarkMapBuilder/131072/baseline-4                         30          38380055 ns/op        22409913 B/op     266298 allocs/op
BenchmarkMapBuilder/131072/immutable-literal-4                 8         131526178 ns/op        63049368 B/op     275657 allocs/op
BenchmarkMapBuilder/131072/immutable-builder-4                12          85273761 ns/op        42729248 B/op     270978 allocs/op
BenchmarkMapRange/10/baseline-4                         10055437               119 ns/op               0 B/op          0 allocs/op
BenchmarkMapRange/10/immutable-4                         8391579               144 ns/op               0 B/op          0 allocs/op
BenchmarkMapRange/1024/baseline-4                          87032             13758 ns/op               0 B/op          0 allocs/op
BenchmarkMapRange/1024/immutable-4                         74726             16041 ns/op               0 B/op          0 allocs/op
BenchmarkMapRange/131072/baseline-4                          657           1817246 ns/op               0 B/op          0 allocs/op
BenchmarkMapRange/131072/immutable-4                         578           2067425 ns/op               0 B/op          0 allocs/op
PASS
ok      go.yhsif.com/immutable  42.700s

Documentation

Overview

Package immutable provides immutable data structures (map/set/list).

Note that immutable map/set/list only guarantee the immutability of the container it self, not the content inside. For example if you are using a immutable list of pointers, you are guaranteed that you always get the same pointer with the same index, but the content pointer points to might be changed by others shared the same immutable list.

Index

• Variables
• type Comparable
• type List
  • func ListLiteral(items ...interface{}) List
• type ListBuilder
  • func NewListBuilder() ListBuilder
• type ListRangeFunc
• type Map
  • func MapLiteral(m MapLiteralType) Map
• type MapBuilder
  • func NewMapBuilder() MapBuilder
• type MapLiteralType
• type MapRangeFunc
• type Set
  • func SetLiteral(items ...Comparable) Set
• type SetBuilder
  • func NewSetBuilder() SetBuilder
• type SetRangeFunc

Examples

• List
• Map
• Map (Wrapped)
• Set

Constants

This section is empty.

Variables

var ErrBreak = errors.New("stop iteration")

ErrBreak can be used in Range functions to stop the iteration early.

Functions

This section is empty.

Types

type Comparable

type Comparable = interface{}

Comparable defines the key type of Map and item type of Set.

It must support go's comparison operators, as defined in: https://golang.org/ref/spec#Comparison_operators

type List

type List interface {
	// Len returns the length of the list.
	Len() int

	// Get returns the i-th item with 0-index.
	//
	// It panics when i is out of [0, Len()-1].
	Get(i int) interface{}

	// Range iterates through the list, in its original order.
	//
	// It will return the error returned by f.
	Range(f ListRangeFunc) error

	// Reslice returns the sublist from start to end-1 index.
	//
	// Use out of range indices will cause panic.
	Reslice(start, end int) List
}

List defines the interface of an immutable list.

Example

package main import ( "fmt" "go.yhsif.com/immutable" ) func main() { list := immutable.ListLiteral("a", "b", "c") fmt.Printf("Len: %d\n", list.Len()) fmt.Println("Break iteration:") list.Range(func(i int, x interface{}) error { if i >= 1 { return immutable.ErrBreak } fmt.Printf("%d: %v\n", i, x) return nil }) fmt.Println("Full iteration:") list.Range(func(i int, x interface{}) error { fmt.Printf("%d: %v\n", i, x) return nil }) fmt.Printf("%%v: %v\n", list) fmt.Println("Reslice(1, 3):", list.Reslice(1, 3)) }

Output:


Len: 3
Break iteration:
0: a
Full iteration:
0: a
1: b
2: c
%v: [a b c]
Reslice(1, 3): [b c]

var EmptyList List = (*list)(nil)

EmptyList defines an immutable empty list.

func ListLiteral

func ListLiteral(items ...interface{}) List

ListLiteral creates an immutable list from items.

It's shorthand for immutable.NewListBuilder().Append(items...).Build().

type ListBuilder

type ListBuilder interface {
	List

	// Append appends item(s) to the list.
	//
	// It should return self for chaining.
	Append(x ...interface{}) ListBuilder

	// Build builds the immutable list.
	Build() List
}

ListBuilder defines the interface of an immutable list builder.

It's not guaranteed to be thread-safe and shouldn't be used concurrently.

func NewListBuilder

func NewListBuilder() ListBuilder

NewListBuilder creates a ListBuilder.

type ListRangeFunc

type ListRangeFunc func(i int, x interface{}) error

ListRangeFunc defines the iteration function for List type.

i will be the 0-based index and x will be the item.

Whenever ListRangeFunc returns a non-nil error, the iteration will be stopped. The error will be returned by Range function.

type Map

type Map interface {
	// Len returns the size of the map.
	Len() int

	// Get returns the value to the key.
	//
	// If the key is not in the map, value will be nil and ok will be false.
	Get(key Comparable) (value interface{}, ok bool)

	// Range iterates through the map.
	//
	// It will return the error returned by f.
	Range(f MapRangeFunc) error
}

Map defines the interface of an immutable map.

Example

package main import ( "fmt" "go.yhsif.com/immutable" ) func main() { m := immutable.MapLiteral(immutable.MapLiteralType{ 1: "a", }) fmt.Printf("%%v: %v\n", m) m = immutable.MapLiteral(immutable.MapLiteralType{ 1: "a", 2: "b", 3: "c", }) fmt.Printf("Len: %d\n", m.Len()) m.Range(func(k immutable.Comparable, v interface{}) error { fmt.Printf("%v: %v\n", k, v) return nil }) }

Output:


%v: map[1:a]
Len: 3
1: a
2: b
3: c

Example (Wrapped)

This example demonstrates how to wrap immutable.Map into a stronger type map (we use int -> string as an example).

package main import ( "fmt" "go.yhsif.com/immutable" ) type ImmutableIntStringMap struct { m immutable.Map } func (m ImmutableIntStringMap) Len() int { return m.m.Len() } func (m ImmutableIntStringMap) Get(key int) (value string, ok bool) { var v immutable.Comparable v, ok = m.m.Get(key) if ok { value = v.(string) } return } func (m ImmutableIntStringMap) Range(f func(key int, value string) error) error { return m.m.Range(func(k immutable.Comparable, v interface{}) error { return f(k.(int), v.(string)) }) } // This example demonstrates how to wrap immutable.Map into a stronger type map // (we use int -> string as an example). func main() { m := ImmutableIntStringMap{ m: immutable.MapLiteral(immutable.MapLiteralType{ 1: "a", 2: "b", 3: "c", }), } fmt.Printf("Len: %d\n", m.Len()) m.Range(func(k int, v string) error { fmt.Printf("%v: %v\n", k, v) return nil }) }

Output:


Len: 3
1: a
2: b
3: c

var EmptyMap Map = (*immutableMap)(nil)

EmptyMap defines an immutable empty map.

func MapLiteral

func MapLiteral(m MapLiteralType) Map

MapLiteral creates an immutable map from existing map.

It's shorthand for immutable.NewMapBuilder().Update(m).Build().

type MapBuilder

type MapBuilder interface {
	Map

	// Set sets the key value pair to the map.
	//
	// It should return self for chaining.
	Set(key Comparable, value interface{}) MapBuilder

	// Update updates every key value pair from m to the map.
	//
	// It should return self for chaining.
	Update(m MapLiteralType) MapBuilder

	// Build builds the immutable map.
	Build() Map
}

MapBuilder defines the interface of an immutable map builder.

It's not guaranteed to be thread-safe and shouldn't be used concurrently.

func NewMapBuilder

func NewMapBuilder() MapBuilder

NewMapBuilder creates a new MapBuilder.

type MapLiteralType

type MapLiteralType map[Comparable]interface{}

MapLiteralType is the shorthand type to be used in MapLiteral.

type MapRangeFunc

type MapRangeFunc func(key Comparable, value interface{}) error

MapRangeFunc defines the iteration function for Map type.

Whenever MapRangeFunc returns a non-nil error, the iteration will be stopped. The error will be returned by Range function.

type Set

type Set interface {
	// Len returns the length of the set.
	Len() int

	// Contains checks whether an item is in the set.
	Contains(x Comparable) bool

	// Range iterates through the set.
	//
	// It will return the error returned by f.
	Range(f SetRangeFunc) error
}

Set defines the interface of an immutable set.

Example

package main import ( "fmt" "go.yhsif.com/immutable" ) func main() { s := immutable.SetLiteral("a") fmt.Printf("%%v: %v\n", s) s = immutable.SetLiteral("a", "b", "c") fmt.Printf("Len: %d\n", s.Len()) s.Range(func(x immutable.Comparable) error { fmt.Printf("%v\n", x) return nil }) }

Output:


%v: [a]
Len: 3
a
b
c

var EmptySet Set = (*set)(nil)

EmptySet defines an immutable empty set.

func SetLiteral

func SetLiteral(items ...Comparable) Set

SetLiteral creates an immutable set from items.

It's shorthand for immutable.NewSetBuilder().Add(items...).Build().

type SetBuilder

type SetBuilder interface {
	Set

	// Add adds item(s) to the set.
	//
	// It should return self for chaining.
	Add(x ...Comparable) SetBuilder

	// Build builds the immutable set.
	Build() Set
}

SetBuilder defines the interface of an immutable set builder.

It's not guaranteed to be thread-safe and shouldn't be used concurrently.

func NewSetBuilder

func NewSetBuilder() SetBuilder

NewSetBuilder creates a new SetBuilder.

type SetRangeFunc

type SetRangeFunc func(x Comparable) error

SetRangeFunc defines the iteration function for Set type.

Whenever SetRangeFunc returns a non-nil error, the iteration will be stopped. The error will be returned by Range function.