UX in network apps: how not to fail
UX in network apps: how not to fail
Close

8 March 2022

Software Development

Generics in Go – definition, history, and examples of use

21 minutes reading

Generics in Go – definition, history, and examples of use

Go 1.18 introduces a new mechanism for generic programming – type parameters. This long-awaited feature finally sees daylight in the officially accepted proposal. 

This article focuses on a complex description of how type parameters work – everything you need to know about Go generics, with examples, in one place. 

Are you interested in more information about the language itself? Check out our previous articles for a Go overview and how it is different from Python

What are generics in Go?

It is common knowledge that Go is a statically-typed programming language. That means any variable or function parameter has a specific type to be declared when writing an application (e.g. string or int) and that type is verified by the compiler during its usage, e.g. on a function call. This approach means that algorithms might be tightly coupled to specific types and not be reusable. 

To be able to create more reusable types and functions, generic programming was invented. It 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. Generic programming is also known as parametric polymorphism.

Till now, Go had built-in generic types (e.g. slice, map, channel) and functions (e.g. append(), copy()). However, there was no capability to create custom generic types and functions. Go 1.18 changes that by introducing type parameters – a mechanism facilitating generic programming. It permits types to be parameters when declaring types and functions. When the generic code runs, the type arguments provided by the caller replace type parameters.

Professional Golang development services

Generic programming substitutes – before Go 1.18

To better understand the reason why generics are needed, let’s implement a reusable algorithm that works with multiple types without using type parameters. We’ll implement a simple function returning the Max number in a given slice of numbers.

We have several approaches to do that:

  • Manual code duplication
  • Code duplication via code generation
  • Passing empty interfaces (interface{}) and unboxing with type assertions
  • Passing empty interfaces (interface{}) and unboxing with reflections
  • Operating on defined interfaces

Implementing the algorithm for each approach will be shown as a focus on their drawbacks. If you are well aware of these problems, feel free to jump to the next chapter – generics history.

Manual code duplication

Developers can simply provide a separate function for each type that needs to be handled.

func MaxInt(s []int) int {
    if len(s) == 0 {
        return 0
    }

    max := s[0]
    for _, v := range s[1:] {
        if v > max {
            max = v
        }
    }
    return max
}

func MaxFloat64(s []float64) float64 {
    if len(s) == 0 {
        return 0
    }

    max := s[0]
    for _, v := range s[1:] {
        if v > max {
            max = v
        }
    }
    return max
}
// Usage
m1 := MaxInt([]int{4, -8, 15})
m2 := MaxFloat64([]float64{4.1, -8.1, 15.1})

While using this method, some drawbacks are worth mentioning – copy-paste requires lots of manual labor, and code duplication lowers the maintainability level. 

Code duplication via code generation

We can automate code duplication by generating the code. This is a widely used technique in the Go ecosystem and there are even tools for it, e.g. genny. However, adding code generation steps to the project's build pipeline increases complexity. Moreover, large amounts of generated code increase compilation times, hurting the developer experience.

Passing empty interfaces and unboxing with type assertions

Another approach is to require the caller to box input data in empty interfaces. The algorithm then can unbox the data using type switches and type assertions. The returned result is also wrapped into an empty interface.

func MaxNumber(s []interface{}) (interface{}, error) {
    if len(s) == 0 {
        return nil, errors.New("no values given")
    }
   switch first := s[0].(type) {
    case int:
        max := first
        for _, rawV := range s[1:] {
            v := rawV.(int)
            if v > max {
                max = v
            }
        }
        return max, nil
    case float64:
        max := first
        for _, rawV := range s[1:] {
            v := rawV.(float64)
            if v > max {
                max = v
            }
        } 
       return max, nil
    default:
        return nil, fmt.Errorf("unsupported element type of given slice: %T", first)
    }
}
// Usage
m1, err1 := MaxNumber([]interface{}{4, -8, 15})
m2, err2 := MaxNumber([]interface{}{4.1, -8.1, 15.1})

The main drawback here is losing type-safety. If the caller passes data of an unsupported type, a properly implemented algorithm should return an error. However bugs could easily cause a panic. Moreover, usability takes a hit as well, because both the caller code and implementation contain wrapping data in empty interfaces and type assertions for boxing/unboxing, respectively.

Passing empty interfaces and unboxing with reflections

Reflection, as a form of metaprogramming, is the capability of a program to examine its structure. We can use that instead of type assertions to unbox data from interface types.

func MaxNumber(s []interface{}) (interface{}, error) {
    if len(s) == 0 {
        return nil, errors.New("no values given")
    }

    first := reflect.ValueOf(s[0])
    if first.CanInt() {
        max := first.Int()
        for _, ifV := range s[1:] {
            v := reflect.ValueOf(ifV)
            if v.CanInt() {
                intV := v.Int()
                if intV > max {
                    max = intV
                }
            }
        }
        return max, nil
    }

    if first.CanFloat() {
        max := first.Float()
        for _, ifV := range s[1:] {
            v := reflect.ValueOf(ifV)
            if v.CanFloat() {
                intV := v.Float()
                if intV > max {
                    max = intV
                }
            }
        }
        return max, nil
    }

    return nil, fmt.Errorf("unsupported element type of given slice: %T", s[0])
}
// Usage
m1, err1 := MaxNumber([]interface{}{4, -8, 15})
m2, err2 := MaxNumber([]interface{}{4.1, -8.1, 15.1})

As in the previous approach, type-safety is lost here. Let’s add to that abysmal readability of the algorithm and we have a recipe for triggering errors and panic due to bugs. Additionally, this method typically has lower performance than others.

Operating on defined interfaces

The algorithm can also expect input data to be passed through a specific, defined interface. This interface should contain all necessary methods that are required to implement the algorithm. In the case of the Max function, those are the Len, Less and Elem methods. Take a look at the definition of the ComparableSlice interface to understand their role.

type ComparableSlice interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with index i has lower value than the element with index j.
    Less(i, j int) bool
    // Elem returns the element with index i.
    Elem(i int) interface{}
}

func MaxNumber(s ComparableSlice) (interface{}, error) {
    if s.Len() == 0 {
        return nil, errors.New("no values given")
    }

    max := s.Elem(0)
    for i := 1; i < s.Len(); i++ {
        if s.Less(i-1, i) {
            max = s.Elem(i)
        }
    }

    return max, nil
}

type ComparableIntSlice []int

func (s ComparableIntSlice) Len() int { return len(s) }
func (s ComparableIntSlice) Less(i, j int) bool { return s[i] < s[j] }
func (s ComparableIntSlice) Elem(i int) interface{} { return s[i] }

type ComparableFloat64Slice []float64

func (s ComparableFloat64Slice) Len() int { return len(s) }
func (s ComparableFloat64Slice) Less(i, j int) bool { return s[i] < s[j] }
func (s ComparableFloat64Slice) Elem(i int) interface{} {return s[i]}
// Usage
m1, err1 := MaxNumber(ComparableIntSlice([]int{4, -8, 15}))
m2, err2 := MaxNumber(ComparableFloat64Slice([]float64{4.1, -8.1, 15.1}))

This approach is used by the Sort function from stdlib. Its key drawback is the fact that it is hard to use, because the caller needs to wrap the data in a custom type implementing the defined interface (ComparableIntSlice in the example above). This is a little more convenient for users when the algorithm code provides such custom types. In the standard library’s Sort case, custom types are provided for two common slices:  IntSlice and Float64Slice.

Summary

As shown above, implementing reusable algorithms handling multiple types in Go comes with a set of substantial issues, depending on the approach used. The type parameters mechanism is a solution that avoids them.

Generics history – what were the proposals and why were they previously rejected?

The history of Go generics is not straightforward. For years this programming language did not have generics. Why, for such a long time, did Go not have them? The answer is simple: implementing generics adds complexity to the language. That might mean breaking one of the principal Go rules—the simplicity of the language. However, the Go community has continuously been asking for this feature to be added since 2009. Every proposal design had significant input from the community—people giving their ideas and insights. Previous proposals were not good enough and, more crucially, not simple enough. The Type Functions proposal was one of the first. There were more attempts after this one, but still none met the requirements. The topic came back in 2019 at GopherCon, where Ian Lance Taylor gave a clear picture of why generics would be implemented and how they would look. A year later, Robert Griesemer announced that the planned changes would be completely compatible with older Go versions, and already existing programs would work without any inconvenience. 

Without further ado, let's look at the proposal that conquered the Go creators and the community’s hearts.

What does the current Go generics proposal look like? 

Rejected proposals for generics have already been highlighted, so now let’s focus on the accepted one. What do current versions of Go code generics look like? 

The accepted proposal covers aspects such as: 

  • new syntax/keywords, 
  • type constraints are interface types, 
  • interface types used as type constraints can have a list of predeclared types,
  • using a generic function or type requires passing type arguments,
  • type arguments of generic function call can be inferred from regular parameters or other known type arguments.

However, the accepted proposal includes many more points than just these. We will take a closer look by using examples in the next section.

Type parameters deep dive

Type parameters fundamentals

To understand Go generics we need to explain several key concepts: type parameter, type argument and type constraint. Let’s take a look at a generic function that returns the first element of a given slice.

func FirstElem[T any](s []T) T {
    return s[0]
}
// Usage
r1 := FirstElem[string]([]string{"Go", "rocks"})
r2 := FirstElem[int]([]int{4, 8, 15})
r3 := FirstElem([]string{"it", "hoge"})

In the example above, “T” is a type parameter. It occurs in the type parameter list in square brackets and in the rest of the function signature. The keyword “any” that can be seen in the type parameter list is a type constraint. Finally, type arguments are placed in the caller code in square brackets just after the function name. These are “string” and “int” in this case.

Each type parameter has a type constraint, which can be thought of as a meta-type. A type constraint specifies the permissible type arguments that the calling code can use for the respective type parameter. In the case of “any” constraint it is a set of all possible Go types. When compiling, the type parameter stands for a single type – the type provided as a type argument by the calling code. A type argument is valid if it implements the type parameter’s constraint.

The compiler might infer type arguments based on function parameters passed by the caller. In the example above, the type argument list is omitted and the compiler deduces it to be “string” from the given slice of strings. 

Type constraints

Type constraints are usually more complicated than the trivial “any”. Let’s take a look at the example of the StringableFloat type constraints below.

type StringableFloat interface {
    ~float32 | ~float64 // union of types
    String() string
}

// MyFloat is a float that satisfies the StringableFloat type constraint.
type MyFloat float64 

func (m MyFloat) String() string {
    return fmt.Sprintf("%e", m)
}

func StringifyFloat[T StringableFloat](f T) string {
    return f.String()
}
// Usage
var f MyFloat = 48151623.42
s := StringifyFloat[MyFloat](f)

In the example above, the StringableFloat type constraint is used as a constraint for the type parameter T of the function StringifyFloat. MyFloat is a type that satisfies that constraint.

The type constraint is declared as an interface containing a union of types and/or methods. In the example, it is both a union of float32 and float64 types, as well as a method String(). The constraint allows any type satisfying the interface, i.e. one of the listed types and  implementing all methods.

The new token “~” has been introduced to make it possible to use custom types as type arguments. “~T” means the set of all types with the underlying type T. Thus MyFloat, which is a custom type based on float64, is allowed by the constraint.

Type constraints can reference other type parameters. One can use that to define a constraint for all slices of any type.

type SliceConstraint[E any] interface {
    ~[]E
}

func FirstElem1[S SliceConstraint[E], E any](s S) E {
    return s[0]
}
// Usage
r1 := FirstElem1([]string{"Go", "rocks"})

Type constraints can be defined directly in the type parameter list. The following functions are equivalent to the previous example.

func FirstElem2[S interface{ ~[]E }, E any](s S) E {
    return s[0]
}

func FirstElem3[S ~[]E, E any](s S) E {
    return s[0]
}
// Usage
s := []string{"Go", "rocks"}
r1 := FirstElem1(s)
r2 := FirstElem2(s)
r3 := FirstElem3(s)

Developers do not need to define all the constraints themselves. Common constraints are provided by the Go team. Two of them are built into the language and several more are defined in the x/exp/constraints package. Note that this package is planned to be incorporated into the standard library in the Go 1.19 release. These constraints are displayed in the table below.

Go generics constraints

Table 1. Go constraints

We can use the Ordered constraint to implement the Max function to see how the result compares with other techniques shown in the earlier part of this article. We’ll use the fact that if all types in the constraint support an operation, that operation may be used with the respective type parameter.

func Max[T constraints.Ordered](s []T) T {
    if len(s) == 0 {
   	 return *new(T)
    }

    max := s[0]
    for _, v := range s[1:] {
   	 if v > max {
   		 max = v
   	 }
    }
    return max
}
// Usage
m1 := Max[int]([]int{4, -8, 15})
m2 := Max([]float64{4.1, -8.1, 15.1})

type customInt int
m3 := Max([]customInt{4, -8, 15})

As you can see, the user can pass any slice of ordered elements to the function, and even type arguments can be omitted, because of the compiler's inference capabilities. Both algorithm and usage are readable as well as type-safe. Perfect!

Compilation

The compiler has been extended with two mechanisms to be able to support the language additions: type inference and instantiation.

During type inference the compiler performs argument type inference and constraint type inference, if possible. Argument type inference deduces unknown type arguments from the types of the ordinary arguments. Constraint type inference deduces unknown type arguments from known type arguments. The latter applies to generic types/functions with multiple type parameters.

During instantiation, the compiler replaces type parameters with type arguments in the entire function/type signature and verifies that each type argument satisfies its constraint. Then, it instantiates an internal function with given type arguments. After that, the behavior of the compiler is the same as prior to Go 1.18, i.e. it performs the invocation step to verify that each ordinary argument can be used as a function parameter (via assignment check).

Summary

As you can see there is a lot of information to absorb. However, you can download Go 1.18 RC1 and play around with the generics on your own terms and check them out for yourself.

Below is a practical example of generics usage. 

Use case - generic set data structure

One possible use case for type parameters is the implementation of a generic, type-safe set data structure. The implementation is pretty straightforward and actually readable with a little bit of fluency in generics. Please focus on function signatures, as implementation of methods is only a detail here.

// Set implements generic set data structure backed by a hash table.
// It is not thread safe.
type Set[T comparable] struct {
    values map[T]struct{}
}

func NewSet[T comparable](values ...T) *Set[T] {
    m := make(map[T]struct{}, len(values))
    for _, v := range values {
   	 m[v] = struct{}{}
    }
    return &Set[T]{
   	 values: m,
    }
}

func (s *Set[T]) Add(values ...T) {
    for _, v := range values {
   	 s.values[v] = struct{}{}
    }
}

func (s *Set[T]) Remove(values ...T) {
    for _, v := range values {
   	 delete(s.values, v)
    }
}

func (s *Set[T]) Contains(values ...T) bool {
    for _, v := range values {
   	 _, ok := s.values[v]
   	 if !ok {
   		 return false
   	 }
    }
    return true
}

func (s *Set[T]) Union(other *Set[T]) *Set[T] {
    result := NewSet[T](s.Values()...)
    for _, v := range other.Values() {
   	 if !result.Contains(v) {
   		 result.Add(v)
   	 }
    }
    return result
}

func (s *Set[T]) Intersect(other *Set[T]) *Set[T] {
    if s.Size() < other.Size() {
   	 return intersect(s, other)
    }
    return intersect(other, s)
}

// intersect returns intersection of given sets. It iterates over smaller set for optimization.
func intersect[T comparable](smaller, bigger *Set[T]) *Set[T] {
    result := NewSet[T]()
    for k, _ := range smaller.values {
   	 if bigger.Contains(k) {
   		 result.Add(k)
   	 }
    }
    return result
}

func (s *Set[T]) Values() []T {
    return s.toSlice()
}

func (s *Set[T]) Size() int {
    return len(s.values)
}

func (s *Set[T]) Clear() {
    s.values = map[T]struct{}{}
}

func (s *Set[T]) String() string {
    return fmt.Sprint(s.toSlice())
}

func (s *Set[T]) toSlice() []T {
    result := make([]T, 0, len(s.values))
    for k := range s.values {
   	 result = append(result, k)
    }
    return result
}
// Usage
s1 := NewSet(4, 4, -8, 15)
s2 := NewSet("foo", "foo", "bar", "baz")
fmt.Println(s1.Size(), s2.Size())  // 3, 3

s1.Add(-16)
s2.Add("hoge")
fmt.Println(s1.Size(), s2.Size())  // 4, 4
fmt.Println(s1.Contains(-16), s2.Contains("hoge"))  // true, true

s1.Remove(15)
s2.Remove("baz")
fmt.Println(s1.Size(), s2.Size())  // 3, 3

fmt.Println(len(s1.Values()), len(s2.Values()))  // 3, 3

s3 := NewSet("hoge", "dragon", "fly")
fmt.Println(s2.Union(s3).Size())  // 5
fmt.Println(s2.Intersect(s3))  // [hoge]

s1.Clear()
s2.Clear()
fmt.Println(s1.Size(), s2.Size())  // 0, 0

The implemented set keeps its data in a map[T]struct{}, where T is a type parameter. Methods only need to put/retrieve keys to the map and compare them with each other. Hence, the built-in comparable constraint, which allows those operations, is sufficient for type parameter T. Most of the code is identical to non-generic set implementation. Even usage examples utilizing type argument inference do not reveal that a generic type is placed underneath.

Generics usage recommendations 

Generics enable developers to implement generic algorithms that are type-safe and have a better readability level. What exactly can generics facilitate? 

  • Functions operating on slices, maps, channels of any element type.

    • Functions doing calculations on elements of slice or map, e.g. max/min/average/mode/standard deviation.
    • Transformation functions for slices or maps, e.g. scale a slice.
    • Functions operating on channels, e.g. combine two channels into single channel.
  • General purpose data structures, e.g. set, multimap, concurrent hash map, graph, tree, linked list.

  • Functions operating on functions, e.g. call given functions in parallel and return a slice of results.

  • When the implementation of a common method looks the same for each type.

The use cases mentioned above are only examples of how generics can be used and how these written functions and data structures can take some weight off your shoulders. 

It is important to mention that using type parameters is not always optimal. If it is sufficient for an algorithm to call a set of specific methods, using a specific interface is still the best way. Especially when implementation of a common method is different for each type. So, common interfaces such as io.Reader are not going anywhere. Using reflections to unbox passed data should also be considered, because it leads to simple to use APIs. For example, the json.Marshal() function taking data as an empty interface is very convenient for users and modifying it to use type parameters would hurt that situation, because the passed data would need to implement specific methods.

As a rule of thumb, it is best to write Go code as usual and only introduce type parameters when one sees boilerplate code handling different types.

The future of Go generics

There is a growing number of libraries using generics. New ones are being created. They mainly involve generic data structures and functional programming constructs. Notable projects are listed below:

Popular libraries, such as emirpasic/gods, are expected to be updated with generic APIs.

Currently, the Go team is working on generic packages in the golang/exp repository:

The packages above are expected to be incorporated into the standard library. In general, the standard library will include generic algorithms in Go 1.19 (which is planned to be released later this year, around August 2022).

Conclusion 

Generics for Go has been the most frequently requested new feature — their lack was often called the biggest shortcoming of this programming language. 

After the upgrade, now is the best time to give Go a chance, but as parameters are a powerful feature, they should not be overused. 

However, generics are not the only reason why this programming language may be a good choice for your project

References

Here are references if you want to dig deeper into generics.

Daniel

Daniel Furman

Software Engineer