Jan 1, 2021
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 ¶
Examples ¶
Constants ¶
Variables ¶
var ErrBreak = errors.New("stop iteration")
ErrBreak can be used in Range functions to stop the iteration early.
Functions ¶
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 ¶
Code:
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))
}
Len: 3 Break iteration: 0: a Full iteration: 0: a 1: b 2: c %v: [a b c] Reslice(1, 3): [b c]
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.
type ListRangeFunc ¶
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 ¶
Code:
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
})
}
%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).
Code:
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
})
}
Len: 3 1: a 2: b 3: c
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.
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 ¶
Code:
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
})
}
%v: [a] Len: 3 a b c
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.
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.
Source Files
Valid 
Stable version