Set Package in Go
Introduction
The set package provides a generic, in-memory finite set data structure for Go. It is built around a Set[T comparable] interface that follows the mathematical definition of a set (an unordered collection of unique elements) backed by a map-based hashSet implementation that gives you $O(1)$ membership, insertion, and removal.
Because it relies on Go generics (Go 1.23 or newer), a single set works with any comparable type: strings, integers, structs, or anything else you can put in a map. The package is both a practical utility and a teaching companion to our book, Set Theory for Beginners, where the same interface is derived step by step in the “Our Own Set Data Structure” chapter.
Installation
To install the package, run the following command:
1go get -u coderscompass.org/set
Usage Example
The example below builds two sets of characters and combines them with a union, an intersection, and a difference.
NewHashSet[T]()creates an empty setInsertadds elementsUnion,Intersection, andDifferencereturn new sets- the
Stringmethod renders a set in roster form{a, b, c}(string elements are sorted lexicographically for stable output).
You can run it directly in the Go Playground.
1package main
2
3import (
4 "fmt"
5
6 "coderscompass.org/set"
7)
8
9func main() {
10 hobbits := set.NewHashSet[string]()
11 fellowship := set.NewHashSet[string]()
12
13 hobbits.Insert("Frodo")
14 hobbits.Insert("Sam")
15 hobbits.Insert("Merry")
16 hobbits.Insert("Pippin")
17
18 fellowship.Insert("Frodo")
19 fellowship.Insert("Sam")
20 fellowship.Insert("Gandalf")
21 fellowship.Insert("Aragorn")
22
23 // Hobbits who are also members of the Fellowship.
24 fmt.Println("Intersection:", hobbits.Intersection(fellowship))
25
26 // Everyone who is either a hobbit or in the Fellowship.
27 fmt.Println("Union: ", hobbits.Union(fellowship))
28
29 // Hobbits not travelling with the Fellowship.
30 fmt.Println("Difference: ", hobbits.Difference(fellowship))
31}
Running it produces:
1Intersection: {Frodo, Sam}
2Union: {Aragorn, Frodo, Gandalf, Merry, Pippin, Sam}
3Difference: {Merry, Pippin}
Available Operations
The Set[T] interface exposes the full set of operations from the book’s Operations on Sets chapter. The package-level CartesianProduct and PowerSet functions cover the remaining constructions.
| Category | Method | Set operation |
|---|---|---|
| Membership & size | Insert, Remove, Contains | Membership ($\in$) |
Cardinality, IsEmpty | Cardinality ($\lvert S\rvert$) | |
| Subset relations | Equals | Unordered equality |
IsSubsetOf, IsSupersetOf | Subset / superset ($\subseteq$, $\supseteq$) | |
IsProperSubsetOf, IsProperSupersetOf | Proper subset / superset ($\subset$, $\supset$) | |
| Algebraic operations | Union | Union ($\cup$) |
Intersection | Intersection ($\cap$) | |
Difference | Difference ($\setminus$) | |
SymmetricDifference | Symmetric difference ($\triangle$) | |
| Conversion | ToSlice, String | Roster form |
| Package-level functions | set.CartesianProduct(s1, s2) | Cartesian product ($\times$) |
set.PowerSet(s) | Power set ($\mathcal{P}(S)$) |
CartesianProduct returns a Set[Pair[T]] of ordered pairs, while PowerSet returns a Set[Set[T]]: all $2^n$ subsets of the input.
Performance
The hashSet implementation stores elements as map keys, giving the following guarantees. Here $n$ and $m$ are the sizes of the two sets involved, respectively.
| Operation | Time complexity |
|---|---|
Insert / Remove / Contains | $O(1)$ |
Intersection | $O(\min(n, m))$ |
Union | $O(n + m)$ |
Difference | $O(m)$ |
CartesianProduct | $O(n \times m)$ |
PowerSet | $O(2^n)$ |
Source Code
The source code is available on GitHub, and the generated API reference is on pkg.go.dev.
The Book
This package is the companion to Set Theory for Beginners, which builds the same Set interface from first principles in its “Our Own Set Data Structure” chapter. Read the book to go deeper on the mathematics behind each operation:
- union and intersection
- regular and symmetric differences
- the Cartesian product
- the power set