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

    This section is empty.

    Variables

    View Source
    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
          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
                      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).

                        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
                                      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.