Skip to content

Instantly share code, notes, and snippets.

@jboursiquot
Last active July 21, 2022 15:56
Show Gist options
  • Save jboursiquot/6a4ceadc846eb40d6be40b92ac7831b6 to your computer and use it in GitHub Desktop.
Save jboursiquot/6a4ceadc846eb40d6be40b92ac7831b6 to your computer and use it in GitHub Desktop.
Generics in 2 Hours

Generics in 2 Hours

Starting with version 1.18, Go supports the concept of generic programming through the introduction of three major concepts to the language:

  • Type parameterization of functions and types
  • Type sets defined by interfaces
  • Type inference

Let's see how these feature enable us to write less code while still retaining the simplicity we've come to expect of Go.

Before Generics

We have need of a function that can accept a list of numbers and return their sum. Our requirements include the need to support both integer and floating point numbers. Prior to Go 1.18, our choices were as follows:

  1. Write multiple functions consisting of the same body but with different signatures to account for the types we want to support.
  2. Use interface{} for our function arguments and type switch inside the function to determine which type we're working with and bahave accordingly.
  3. Use reflection to determine type information at runtime.

While these options are workable and even acceptable in certain situations, they're not ideal. Let's see some examples of the first two implementations.

To take advantage of the compiler's type checks, we implement two functions, one for each kind of number.

func sumInts(numbers []int) int {
	var s int
	for _, n := range numbers {
		s += n
	}
	return s
}

func sumFloats(numbers []float32) float32 {
	var s float32
	for _, n := range numbers {
		s += n
	}
	return s
}

While these functions solve our problem for the most part, we can observe a great deal of duplication between them. We can try to refactor these functions into a single one by using the interface{}.

func sum(numbers []interface{}) interface{} {
	var s float32
	for _, n := range numbers {
		switch n.(type) {
		case int:
			s += float32(n.(int))
		case float32:
			s += n.(float32)
		default:
			fmt.Printf("unsupported type: %T\n", n)
			continue
		}
	}
	return s
}

The version with the interface{} suffers from a couple of problems. The first is the lack of type safety that interface{} brings with it since the compiler can no longer check the types of values with which we're invoking the function. The second problem is that supporting additional types (e.g. float64) now means adding another case to our type switch. We must also take care of ignoring the types we don't support. Overall, we spend a lot of time doing type-handling within the body of the function ourselves. Type parameterization can help here.

Type Parameters

Generic Functions

Functions that are meant to be generic are written in such a way as to support multiple types. In Go, this is done with a type parameter list:

[P, Q constraint1, R constraint2]

These type parameters are just like ordinary parameter lists but use square brackets instead of parentheseses. Uppercase letters are typically used to represent the types but you can use whatever suits your needs best.

We can refactor our sum function to be generic using type parameters. With type parameters, you can omit explicit concrete types declarations and still have compile time checks, something you couldn't do with inteface{}. Let's see what the syntax looks like.

func sum[T constraints.Ordered](numbers []T) T {
	var s T
	for _, n := range numbers {
		s += n
	}
	return s
}

The above function uses the Ordered interface in the newly-introduced (as of 1.18) constraints package (golang.org/x/exp/constraints), defined as follows:

type Ordered interface {
	Integer | Float | ~string
}

We could have also specified a union of types (using a pipe delimiter |) to specify the list of types as shown below:

func sum[T int | float32](numbers []T) T {
	var s T
	for _, n := range numbers {
		s += n
	}
	return s
}

The list of types specified in the square brakets following the function identifier are the type parameters that the function supports, mainly int and float32. T is a conventional name used to indicate the type that the compiler will ultimately be checking when you invoke the function. T is used as part of the function's signature, mainly to indicate that we'll pass in a list of numbers of type T.

ints := []int{1, 2, 3}
result := sum[int](ints)
fmt.Printf("sum(%v) = %v\n", ints, result) //sum([1 2 3]) = 6

Since Go can infer the type you are invoking the function with, you can omit the type list when calling the function.

floats := []float32{1.1, 2.2, 3.3}
result := sum(floats)
fmt.Printf("sum(%v) = %v\n", floats, result) //sum([1.1 2.2 3.3]) = 6.6

When the compiler comes across sum[int](ints) it performs an "instantiation" of the generic function to obtain a non-generic version that will then be executed. In other words, sum[int](ints) is evaluated as (sum[int])(ints) and sum(floats) as (sum[float32])(floats). More in inference soon.

Playground

Generic Types

Types support type parameter lists too! In the implementation below, a custom type tree with an underlying type struct has a parameter list that allows for any type (as defined by interface{}).

type tree[T interface{}] struct {
	left, right *tree[T]
	val         T
}

func (t *tree[T]) find(v T) *tree[T] { return nil }
	
intTree := tree[int]{}

Exercise 1

Now that you understand the basics of writing generic functions with type parameters in Go, it's time to try it for yourself.

Your task is to refactor this program to use type parameters. Write a single function that can accept a value of any type to replace the 3 separate functions we currently have.

package main

import "fmt"

func printString(s string) { fmt.Println(s) }

func printInt(i int) { fmt.Println(i) }

func printBool(b bool) { fmt.Println(b) }

func main() {
	printString("hello")
	printInt(5)
	printBool(false)
}

Solution: https://go.dev/play/p/aD-O8FtOIek

Type Sets

Let's take another look at our generic sum function:

func sum[T int | float32](numbers []T) T {
	var s T
	for _, n := range numbers {
		s += n
	}
	return s
}

We can think of the parameter list [T int | float32] as a set of constraints we place on the possible types we're allowed to send in when we invoke the function. Go lets us declare these constraints more readably by taking advantage of interfaces used as type constraints.

Type Constraints are Interfaces

Prior to Go 1.18, interface types were seen only as defining method sets. Any type that implemented all of the methods in the set defined by an interface was said to satisfy that interface. With Go 1.18, another way we look at interfaces is that they also define type sets, namely the types that implement the method methods of the interface. Meaning, any type that is an element of the interface’s type set implements the interface.

See illustrations at https://go.dev/blog/intro-generics

type numeric interface{
	int | float32
}

func sum[T numeric](numbers []T) T {
	var s T
	for _, n := range numbers {
		s += n
	}
	return s
}

Type numeric is an interface with a type list built into it and usable by our sum function. This makes extending the list of supported types simple as well. If one day we needed to support float64, we'd simply add it to the type list.

type numeric interface{
	int | float32 | float64
}
nums := []float64{1, 2.2, 3.3}
result := sum(nums)
fmt.Printf("sum(%v) = %v\n", nums, result) // sum([1 2.2 3.3]) = 6.5

Note that you cannot mix the types of values you invoke the function with by attempting to use the interface type:

nums := []numeric{1, 2.2, 3.3} // will not work
result := sum(nums)
fmt.Printf("sum(%v) = %v\n", nums, result)
./prog.go:20:12: interface contains type constraints

Custom types with primitive underlying types can also be used in type constraints using the ~ (tilde) token like so:

type mySpecialInt int

type numeric interface {
	~int | ~float32 | ~float64
}

Here, we're specifying that the numeric interface supports any type that is or that has int, float32, or float64 as an underlyting type.

nums := []mySpecialInt{1, 2, 3}
result := sum(nums)
fmt.Printf("sum(%v) = %v\n", nums, result) // sum([1 2 3]) = 6

Exercise 2

Write a generic sumSlice function that takes a slice which supports all unsigned types (i.e. uint, uint8, uint16, uint32, uint64, and uintptr), including any custom type that has one of these base types as its underlying type, and returns the sum of all its elements.

Hint: Does the standard library offer something useful here?

Solution: https://go.dev/play/p/Jawb-8Ra6Fa

Type Inference

Type inference is perhaps the feature that lets us write generics in as natural a way as we're used to in Go. There are two types of inference at play: function argument type inference and constraint type inference.

Function argument type inference

Consider one of our previous examples:

func sum[T constraints.Ordered](numbers []T) T {
	var s T
	for _, n := range numbers {
		s += n
	}
	return s
}

Given that the signature of the generic function includes type parameters, calling this function would also necessitate that we pass in type arguments:

func main(){
	nums := []float64{1, 2.2, 3.3}
	result := sum[float64](nums) // explicit type argument
	fmt.Printf("sum(%v) = %v\n", nums, result)
}

The good news is that the compiler can infer the type argument for T in such cases.

func main(){
	nums := []float64{1, 2.2, 3.3}
	result := sum(nums) // inferred type argument
	fmt.Printf("sum(%v) = %v\n", nums, result)
}

The inferrence works because the compiler can match the type of the argument nums with the type of the parameter numbers in the function signature.

Constraint type inference

Consider the following grow function which takes a slice of elements of type E constrained to integer values and grows each element by the given factor, also of type E:

func grow[E constraints.Integer](slice []E, factor E) []E {
	res := make([]E, len(slice))
	for i, n := range slice {
		res[i] = n * factor
	}
	return res
}

Also consider the following data type:

type data []int

func (c data) String() string { return "" }

Let's assume we want a function to "grow" and "show" a value of type data like so:

func growAndShow(d data) {
	res := grow(d, 5)
	fmt.Println(res.String()) // oops!
}

At the point where we call res.String() we'll encounter a undefined (type []int has no field or method String) error. This is because the type of the value returned from grow is not data but the underlying type of data itself, []int. In other words, as written, the grow function returns []E where E is the element type of the argument slice.

To resolve this, we'll modify our grow function to use a type parameter for the slice type:

func grow[D ~[]E, E constraints.Integer](slice D, factor E) D {
	res := make(D, len(slice))
	for i, n := range slice {
		res[i] = n * factor
	}
	return res
}

Here's what we've done:

  1. We add a new type parameter D for the type of the slice argument
  2. We constrain it such that its underlying type is D rather than []E
  3. We change the return type to D
  4. E is still constrained to integers
  5. We update the function body to now use D instead of []E

Now calling the growAndShow function once more should yeild no errors because the return type of grow is now D and not []int as before.

Looking at our growAndShow function again, we see that we still didn't need to be explicit with our call to grow:

func growAndShow(d data) {
	res := grow[data, int](d, 5) // type arguments not necessary here
	fmt.Println(res.String())
}

Type arguments can be omitted because the revised grow function has D and E parameters, whereas if type arguments aren't passed in when it is called, function type argument inference kicks in, letting the compiler infer that the type argument for D is data. Determining the type for the second argument E uses a process called "constraint type inference."

Constraint type inference deduces type arguments from type parameter constraints. It is used when one type parameter has a constraint defined in terms of another type parameter. When the type argument of one of those type parameters is known, the constraint is used to infer the type argument of the other. (Source https://go.dev/blog/intro-generics)

A deeper dive into constraint type inference can be had in the proposal and spec(https://go.dev/ref/spec).

In practice...

type inference either succeeds or fails. If it succeeds, type arguments can be omitted, and calling generic functions looks no different than calling ordinary functions. If type inference fails, the compiler will give an error message, and in those cases we can just provide the necessary type arguments. (Source https://go.dev/blog/intro-generics)

Emerging Patterns

As the use of generics starts to spread, best practices and patterns will also emerge. The following are just a handful of observations of the types of approaches the community is starting to explore.

Standard Library Constraints

There are common sets of interfaces that the Go standard library makes available today for use as part of the constraints experimental package.

As more use cases come up, Go will standardize certain constraints like we see early signs of in the form of the golang.org/x/exp/constraints package.

We can refactor our type constraint to use the constraints package.

import "golang.org/x/exp/constraints"

type numeric interface{
	constraints.Integer | constrainst.Float
}

Looking at the standard library's definition of constraints.Integer we see that it uses two other interfaces, Signed and Unsigned:

type Integer interface {
	Signed | Unsigned
}

type Signed interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
}

type Unsigned interface {
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

Using constraints.Integer in our own type constraint lets us take advantage of a standard definition across package boundaries.

There's one more thing to call out here as well. Did you notice the tilde (~) in front of some of the concrete types used in the parameter lists? It's a new symbol used to inform the compiler that we're okay with our concrete types being used as underlying types and is refered to as an "approximation element." Here's what that translates to:

type numeric interface{
	~int | ~float32
}

type customNumber int

func sum[T numeric](numbers []T) T {
	var s T
	for _, n := range numbers {
		s += n
	}
	return s
}

func main() {
		numbers := []customNumber{1, 2, 3}
		fmt.Printf("sum(%v) = %v\n", numbers, sum(numbers)) //sum([1 2 3]) = 6 
}

In the above program we modify our numeric type constraint to include approximations for the int and float32 types, thereby allowing any custom type that uses these builtin types as their underlying type to satisfy the type constraint.

Our customNumber custom type, using int as its underlying type, is allowed to be used as a valid type for calling on sum.

Generic Data Structures

type node[T any] struct {
   val  T
   next *Node[T]
}

func (n *node[T]) add(next *node[T]) {
   n.next = next
}

Using Predeclared Identifiers: Comparables

Go 1.18 adds an additional predeclared identifier known as comparable which when used as the type for a parameter means that values of that type can be compared with one another using the == and != operators.

See language spec for more: https://go.dev/ref/spec on predeclared identifiers.

Let's say we needed a way to get all the keys from a map. One implementation using comparable looks like this:

// https://go.dev/play/p/2FycmAnxj-b

func keys[K comparable, V any](m map[K]V) []K {
	r := make([]K, 0, len(m))
	for k := range m {
		r = append(r, k)
	}
	return r
}

func main() {
	m := map[string]int{"a": 1, "b": 2, "c": 3}
	fmt.Println(keys(m)) // [a b c]
}

Other notables

When to use Generics

While best practices are still emerging, there are a common set of use cases that the community seems to be agreeing on:

  • General purpose data structures such as binary trees, heaps, linked lists, etc. Element types can be factored out of those using parameter lists.
  • When the same method shows up over and over for multiple types.
  • Working with slices, maps, and channels of any type.

For example, merging of channels:

func merge[T any](chan1, chan2 <-chan T) <-chan T {
	// not implemented
}

When to avoid Generics

When you just need to call a method of the type argument you don't need generics.

// Don't do this. Generics does nothing for you here.
func writeSomeBits[T io.Writer](w T) {
   b := ...
   _, _ = w.Write(b)
}
func readSomeBits(w io.Writer) {...}// Just do this

When the implementation of a common method is different for each type.

When the operation is different for each type, even without a method.

Key Takeaway: Write code, don't design types. Don't use type parameters prematurely but rather wait until you are about to write boilerplate.

Resources

Summary

In this section you learned about writing generic functions, how to constrain the types they support, and some of the nuances you need to be aware of when declaring and accepting types.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment