• Stars
    star
    713
  • Rank 63,511 (Top 2 %)
  • Language
    Go
  • License
    MIT License
  • Created over 5 years ago
  • Updated about 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Immutable collections for Go

Immutable release test coverage license

This repository contains generic immutable collection types for Go. It includes List, Map, SortedMap, Set and SortedSet implementations. Immutable collections can provide efficient, lock free sharing of data by requiring that edits to the collections return new collections.

The collection types in this library are meant to mimic Go built-in collections such asslice and map. The primary usage difference between Go collections and immutable collections is that immutable collections always return a new collection on mutation so you will need to save the new reference.

Immutable collections are not for every situation, however, as they can incur additional CPU and memory overhead. Please evaluate the cost/benefit for your particular project.

Special thanks to the Immutable.js team as the List & Map implementations are loose ports from that project.

List

The List type represents a sorted, indexed collection of values and operates similarly to a Go slice. It supports efficient append, prepend, update, and slice operations.

Adding list elements

Elements can be added to the end of the list with the Append() method or added to the beginning of the list with the Prepend() method. Unlike Go slices, prepending is as efficient as appending.

// Create a list with 3 elements.
l := immutable.NewList[string]()
l = l.Append("foo")
l = l.Append("bar")
l = l.Prepend("baz")

fmt.Println(l.Len())  // 3
fmt.Println(l.Get(0)) // "baz"
fmt.Println(l.Get(1)) // "foo"
fmt.Println(l.Get(2)) // "bar"

Note that each change to the list results in a new list being created. These lists are all snapshots at that point in time and cannot be changed so they are safe to share between multiple goroutines.

Updating list elements

You can also overwrite existing elements by using the Set() method. In the following example, we'll update the third element in our list and return the new list to a new variable. You can see that our old l variable retains a snapshot of the original value.

l := immutable.NewList[string]()
l = l.Append("foo")
l = l.Append("bar")
newList := l.Set(2, "baz")

fmt.Println(l.Get(1))       // "bar"
fmt.Println(newList.Get(1)) // "baz"

Deriving sublists

You can create a sublist by using the Slice() method. This method works with the same rules as subslicing a Go slice:

l = l.Slice(0, 2)

fmt.Println(l.Len())  // 2
fmt.Println(l.Get(0)) // "baz"
fmt.Println(l.Get(1)) // "foo"

Please note that since List follows the same rules as slices, it will panic if you try to Get(), Set(), or Slice() with indexes that are outside of the range of the List.

Iterating lists

Iterators provide a clean, simple way to iterate over the elements of the list in order. This is more efficient than simply calling Get() for each index.

Below is an example of iterating over all elements of our list from above:

itr := l.Iterator()
for !itr.Done() {
	index, value, _ := itr.Next()
	fmt.Printf("Index %d equals %v\n", index, value)
}

// Index 0 equals baz
// Index 1 equals foo

By default iterators start from index zero, however, the Seek() method can be used to jump to a given index.

Efficiently building lists

If you are building large lists, it is significantly more efficient to use the ListBuilder. It uses nearly the same API as List except that it updates a list in-place until you are ready to use it. This can improve bulk list building by 10x or more.

b := immutable.NewListBuilder[string]()
b.Append("foo")
b.Append("bar")
b.Set(2, "baz")

l := b.List()
fmt.Println(l.Get(0)) // "foo"
fmt.Println(l.Get(1)) // "baz"

Builders are invalid after the call to List().

Map

The Map represents an associative array that maps unique keys to values. It is implemented to act similarly to the built-in Go map type. It is implemented as a Hash-Array Mapped Trie.

Maps require a Hasher to hash keys and check for equality. There are built-in hasher implementations for most primitive types such as int, uint, and string keys. You may pass in a nil hasher to NewMap() if you are using one of these key types.

Setting map key/value pairs

You can add a key/value pair to the map by using the Set() method. It will add the key if it does not exist or it will overwrite the value for the key if it does exist.

Values may be fetched for a key using the Get() method. This method returns the value as well as a flag indicating if the key existed. The flag is useful to check if a nil value was set for a key versus a key did not exist.

m := immutable.NewMap[string,int](nil)
m = m.Set("jane", 100)
m = m.Set("susy", 200)
m = m.Set("jane", 300) // overwrite

fmt.Println(m.Len())   // 2

v, ok := m.Get("jane")
fmt.Println(v, ok)     // 300 true

v, ok = m.Get("susy")
fmt.Println(v, ok)     // 200, true

v, ok = m.Get("john")
fmt.Println(v, ok)     // nil, false

Removing map keys

Keys may be removed from the map by using the Delete() method. If the key does not exist then the original map is returned instead of a new one.

m := immutable.NewMap[string,int](nil)
m = m.Set("jane", 100)
m = m.Delete("jane")

fmt.Println(m.Len())   // 0

v, ok := m.Get("jane")
fmt.Println(v, ok)     // nil false

Iterating maps

Maps are unsorted, however, iterators can be used to loop over all key/value pairs in the collection. Unlike Go maps, iterators are deterministic when iterating over key/value pairs.

m := immutable.NewMap[string,int](nil)
m = m.Set("jane", 100)
m = m.Set("susy", 200)

itr := m.Iterator()
for !itr.Done() {
	k, v := itr.Next()
	fmt.Println(k, v)
}

// susy 200
// jane 100

Note that you should not rely on two maps with the same key/value pairs to iterate in the same order. Ordering can be insertion order dependent when two keys generate the same hash.

Efficiently building maps

If you are executing multiple mutations on a map, it can be much more efficient to use the MapBuilder. It uses nearly the same API as Map except that it updates a map in-place until you are ready to use it.

b := immutable.NewMapBuilder[string,int](nil)
b.Set("foo", 100)
b.Set("bar", 200)
b.Set("foo", 300)

m := b.Map()
fmt.Println(m.Get("foo")) // "300"
fmt.Println(m.Get("bar")) // "200"

Builders are invalid after the call to Map().

Implementing a custom Hasher

If you need to use a key type besides int, uint, or string then you'll need to create a custom Hasher implementation and pass it to NewMap() on creation.

Hashers are fairly simple. They only need to generate hashes for a given key and check equality given two keys.

type Hasher[K any] interface {
	Hash(key K) uint32
	Equal(a, b K) bool
}

Please see the internal intHasher, uintHasher, stringHasher, and byteSliceHasher for examples.

Sorted Map

The SortedMap represents an associative array that maps unique keys to values. Unlike the Map, however, keys can be iterated over in-order. It is implemented as a B+tree.

Sorted maps require a Comparer to sort keys and check for equality. There are built-in comparer implementations for int, uint, and string keys. You may pass a nil comparer to NewSortedMap() if you are using one of these key types.

The API is identical to the Map implementation. The sorted map also has a companion SortedMapBuilder for more efficiently building maps.

Implementing a custom Comparer

If you need to use a key type besides int, uint, or string or derived types, then you'll need to create a custom Comparer implementation and pass it to NewSortedMap() on creation.

Comparers on have one methodβ€”Compare(). It works the same as the strings.Compare() function. It returns -1 if a is less than b, returns 1 if a is greater than b, and returns 0 if a is equal to b.

type Comparer[K any] interface {
	Compare(a, b K) int
}

Please see the internal defaultComparer for an example, bearing in mind that it works for several types.

Set

The Set represents a collection of unique values, and it is implemented as a wrapper around a Map[T, struct{}].

Like Maps, Sets require a Hasher to hash keys and check for equality. There are built-in hasher implementations for most primitive types such as int, uint, and string keys. You may pass in a nil hasher to NewSet() if you are using one of these key types.

Sorted Set

The SortedSet represents a sorted collection of unique values. Unlike the Set, however, keys can be iterated over in-order. It is implemented as a B+tree.

Sorted sets require a Comparer to sort values and check for equality. There are built-in comparer implementations for int, uint, and string keys. You may pass a nil comparer to NewSortedSet() if you are using one of these key types.

The API is identical to the Set implementation.

Contributing

The goal of immutable is to provide stable, reasonably performant, immutable collections library for Go that has a simple, idiomatic API. As such, additional features and minor performance improvements will generally not be accepted. If you have a suggestion for a clearer API or substantial performance improvement, please open an issue first to discuss. All pull requests without a related issue will be closed immediately.

Please submit issues relating to bugs & documentation improvements.

More Repositories

1

litestream

Streaming replication for SQLite.
Go
10,958
star
2

thesecretlivesofdata

Understanding what your bits do when you're not looking.
JavaScript
3,440
star
3

wtf

WTF Dial is an example web application written in Go.
Go
1,682
star
4

postlite

Postgres wire compatible SQLite proxy.
Go
1,216
star
5

clock

Clock is a small library for mocking time in Go.
Go
677
star
6

ego

An ERB-style templating language for Go.
Go
581
star
7

testing

A small collection of functions for Go testing.
Go
529
star
8

megajson

A JSON parser generator for high performance encoding and decoding in Go.
Go
466
star
9

hashfs

Implementation of io/fs.FS that appends SHA256 hashes to filenames to allow for aggressive HTTP caching.
Go
358
star
10

sql-parser

Toy SQL parser example for Gopher Academy
Go
330
star
11

genesis

A simple tool for embedding assets in a Go binary.
Go
299
star
12

phantomjs

Go client for PhantomJS.
Go
293
star
13

jmphash

Implementation of the Jump Consistent Hash algorithm in Go.
Go
154
star
14

scuttlebutt

A daemon for tracking and tweeting trending Github repositories by language.
Go
151
star
15

llvm-c-kaleidoscope

An implementation of the Kaleidoscope language using Flex, Bison & the LLVM-C bindings.
C
129
star
16

playback.js

A library for dynamic timeline playback.
JavaScript
118
star
17

litestream-docker-example

An example of using Litestream within a Docker container.
Go
97
star
18

litestream-s6-example

Example repository for building a multi-process Docker container.
Dockerfile
87
star
19

tmpl

Command line interface to Go's text/template library.
Go
84
star
20

css

W3C-compliant CSS3 parser and scanner
Go
83
star
21

grapevine

Trending topics for stuff you care about
Ruby
80
star
22

slowweb

An HTTP request governor
Ruby
75
star
23

litestream-read-replica-demo

A demo application for running live read replication on fly.io with Litestream
Go
69
star
24

ghfs

FUSE Filesystem for the GitHub API
Go
61
star
25

agency

A fast user agent string parser for Go.
Go
60
star
26

litestream-library-example

Example repository for embedding Litestream in a Go application.
Go
56
star
27

litestream-read-replica-example

An example of using Litestream's live read replication feature.
Go
52
star
28

melomel

External ActionScript Interface.
ActionScript
42
star
29

litestream.io

SCSS
40
star
30

pprofdump

A simple utility for collecting net/http/pprof profiles.
Go
28
star
31

peapod

A personal podcast service.
Go
26
star
32

application-development-using-boltdb

Repository for my "Application Development Using BoltDB" talk
Go
26
star
33

sieve

A command line utility for graphing piped data.
Go
23
star
34

production-sqlite-go

Companion repository for GopherCon presentation on "Production Applications Using SQLite & Go"
Go
23
star
35

goo

Thin wrapper for the Go toolchain.
Go
20
star
36

burger-stack

Presentation for "The Burger Stack"
19
star
37

structuring-applications-for-growth

GopherCon 2016 presentation for "Structuring Applications for Growth"
18
star
38

stack

Go debug/stack utility functions.
Go
18
star
39

myapp

An simple application with an HTTP server & SQLite database.
Go
14
star
40

glee

Incomplete Go port of the KLEE SymEx system.
Go
14
star
41

melomel.rb

An external interface to Flash from Ruby.
Ruby
13
star
42

raft.js

An experimental Raft implementation in Javascript.
13
star
43

vex

Variable-length, lexicographically-sortable hex format for uint64 values.
Go
13
star
44

gha

SQLite load testing application using GitHub Archive data.
Go
13
star
45

writing-a-distributed-systems-library

Companion code for the Gopher Academy blog post.
Go
11
star
46

roommate

A conference room scheduling application.
Go
10
star
47

tiny-ego

A toy application showcasing ego templates & components.
Go
10
star
48

boxer

A little app that boxes my time.
Go
10
star
49

bootstrap-ego

An ego template component library for Bootstrap 4.
Go
10
star
50

seppuku

To be executed upon implementation of generics in Go.
Go
10
star
51

syncutil

A collection of utility functions for Go synchronization.
Go
9
star
52

gist

Gist hosting and embedding.
Go
8
star
53

melomel-examples

Examples of using Melomel.
Ruby
8
star
54

describe.today

A web site to describe today.
JavaScript
7
star
55

minipack

A lightweight C MessagePack parser.
C
7
star
56

skybox

An open source funnel analysis application.
Go
7
star
57

go-raft-runner

A test runner application for the go-raft library.
Go
6
star
58

http-wiretap

It's like Charles Proxy for your Rubies!
Ruby
5
star
59

sqlite-bench

Miscellaneous Go/SQLite benchmarks
Go
5
star
60

mincore

Example usage for using mincore() in Go.
Go
5
star
61

miniviz

A simplified interface to GraphViz for laying out clusters, nodes and edges.
Ruby
5
star
62

graphviz-as3

An interface to the graphviz CLI using Adobe AIR.
ActionScript
5
star
63

edb

A simple database for tracking events.
Go
5
star
64

rationl

Online journal for tracking experiments.
Go
4
star
65

hackerbeeper

A dumb utility for playing generated notes when you type.
Go
4
star
66

opus

Command line utility for printing columnized code.
4
star
67

mockdown.as

A Markdown-inspired Mockup Language
ActionScript
4
star
68

serialkiller

ActionScript JSON & XML serialization library
ActionScript
4
star
69

whodump

A command line interface for checking domain name availability.
Ruby
4
star
70

tsld.js

Core library for "The Secret Lives of Data" project.
JavaScript
3
star
71

bandicoot

A crash reporter library for C applications.
C
3
star
72

skydb.io

The Official Sky Web Site
CSS
2
star
73

chatter

Demo application using Server Side Events (SSE) and written in Go.
Go
2
star
74

cine

A movie search application.
Go
2
star
75

authoritarian

Command line utility for authorizing Twitter users to an application.
2
star
76

constdump

Utility for printing a list of package-level constants.
Go
2
star
77

matlock

Simple name extraction utility.
Ruby
2
star
78

d3.jquery.js

A collection of D3.js charts made available as jQuery plugins.
JavaScript
1
star
79

mockdown.rb

Mockups for hackers
Ruby
1
star
80

landmarkd

The Landmark Tracking Server.
Go
1
star
81

httpng

A local server for saving HTML elements as PNG files.
JavaScript
1
star
82

ldbchk

Runs concurrency tests against LevelDB & Levigo.
Go
1
star
83

timeshifter

A Ruby library for shifting time.
Ruby
1
star
84

whollydeliciousfoods.com

The home page for Wholly Delicious Foods.
JavaScript
1
star
85

homebrew-litestream

Homebrew tap for litestream.
Ruby
1
star
86

bench-c

A small collection of benchmarks for the C programming language.
C
1
star
87

unistat

A utility for calculating simple statistics on unicode characters.
Go
1
star
88

gitcoin

Turing gitcoin repository
Go
1
star
89

termgraf

Terminal chronograf
Go
1
star
90

locald

A simple HTTP server for serving static files out of the current directory.
1
star
91

skylandlabs.github.com

Skyland Labs Blog
JavaScript
1
star
92

fql-editor

An editor for FQL queries.
ActionScript
1
star
93

tip.litestream.io

Mirror of litestream.io repository for latest changes.
HTML
1
star
94

prog

Go testing
Go
1
star
95

fslice

A small utility for extracting delimited sections of a file.
Go
1
star
96

ego-example

A simple ego templating example.
Go
1
star