Implementing Set data structure in Go using generics
Generic programming is a style of computer programming in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as parameters.
Go published a contracts draft last year as part go v2 which had support for generics in golang.
They published a new update on 16th June 2020 regarding generics. They introduced typed parameters instead of contracts as experimental feature and will be released as part of go v1.17 in August 2021. This version can be installed from dev.go2go branch or you can use online playground to experiment with generics using type parameters.
Lets see how we can implement Set data structure using generics for all comparable data types.
In computer science, a set is an abstract data type that can store unique values, without any particular order. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set.
Set can be easily implemented in Go using map in go
// Declaring new data type
type Set(type T comparable) map[T]bool
// T is the generic type it can be any comparable data type// Constructor to create new set
// Example :- New(int)() to create a int set
// New(string)() to create a string set
func New(type T comparable)() Set(T) {
return make(Set(T))
}
Implementation of few set methods
// Add values to set
func (s Set(T)) Add(values ...T) {
for _, value := range values {
s[value] = true
}
}// Delete values from set
func (s Set(T)) Delete(values ...T) {
for _, value := range values {
delete(s, value)
}
}// Length of set
func (s Set(T)) Len() int {
return len(s)
}// Method to check if element exists in set
func (s Set(T)) Has(value T) bool {
_, ok := s[value]
return ok
}// Iterate over set using a callback
func (s Set(T)) Iterate(it func(T)) {
for v := range s {
it(v)
}
}// Convert set to slice of values
func (s Set(T)) Values() []T {
values := make([]T, s.Len())
s.Iterate(func(value T) {
values = append(values, value)
})
return values
}// Clone set
func (s Set(T)) Clone() Set(T) {
set := make(Set(T))
set.Add(s.Values()...)
return set
}// Union of 2 sets
func (s Set(T)) Union(other Set(T)) Set(T) {
set := s.Clone()
set.Add(other.Values()...)
return set
}// Intersection of 2 sets
func (s Set(T)) Intersection(other Set(T)) Set(T) {
set := make(Set(T))
s.Iterate(func(value T) {
if other.Has(value) {
set.Add(value)
}
})
return set
}
Before introduction of generics we had to implement this for all data types.
Now we can have a single implementation for all types
// Example on how to use it// Iterator function is a utility to print values
it := func(val int){
fmt.Println(val)
}// Creating set of ints
set1 := New(int)()
// Adding elements
set1.Add(1,2,3,4,2,4)
set2 := New(int)()
set2.Add(3,4,5,6,7)// Union of set prints 1 2 3 4 5 6 7
fmt.Println("union")
set1.Union(set2).Iterate(it)// Intersection of set prints 3 4
fmt.Println("intersection")
set1.Intersection(set2).Iterate(it)
This is one of the basic examples of using generics. It is a powerful tool in many of cases. There are lot of features to explore. You can find the complete details here in contracts draft.
Here is link to playground with above code https://go2goplay.golang.org/p/mNkUG7ap8xv
Github link https://github.com/crushers-lab/go-set
Cons of using generics
Generics comes with cost. Go runtime needs additional cost to use reflect to find the data types etc. So it will be slower compared to non generic implementation.
References
Contracts draft :- https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-contracts.md
Type parameters draft :- https://go.googlesource.com/proposal/+/refs/heads/master/design/go2draft-type-parameters.md
Update on generics :- https://blog.golang.org/generics-next-step
Go v2 Playground :- https://go2goplay.golang.org/
Link to playground :- https://go2goplay.golang.org/p/mNkUG7ap8xv
Link to github :- https://github.com/crushers-lab/go-set
