Generics Are the Generics of Go
Go now includes its most requested feature
About five years ago, I was working on a pull request approval manager for GitHub written in Go called Checks-Out. While building out the integration layer, I came across a situation where the straightforward approach in Go was overly repetitive. The ideal solution would have been to use generics, but they weren't available.
However, I figured out that in many cases, you can use closures to pass values. I described my experience with this problem, and my solution in a blog post and a talk, both called Closures are the Generics of Go.
Things have changed. Starting with Go 1.18, the language includes an implementation of generics using parameterized types. It adds most of the generics functionality that people have requested, without changing the fundamental character of Go.
Introducing Generics in Go
Go is an intentionally small language whose design favors good tooling and readability over features. The Go team also values backwards compatibility; old code should continue to work so that it can be maintained for years. The generics draft was written with these goals in mind.
We'll start our look at Go generics by trying out the simplest case: a user-defined container type. We'll use a linked list as our sample container type. Here's what it looks like to write one in Go before generics:
type LinkedList struct {
value interface{}
next *LinkedList
}
And here's what that looks like when using generics:
type LinkedList[type T] struct {
value T
next *LinkedList[T]
}
It takes three small changes to change this type into a generic type:
- Place '
[T any]'after the type name and before the struct literal. T is the name we'll use as the placeholder for whatever type is supplied when our linked list is used. Many other languages use T as the placeholder type name for a generic type, and it's likely that Go will adopt the same custom. If you need to refer to additional types within the same type or function, use other capital letters; we'll see that in a bit. - Use
Tfor thevaluefield's type instead ofinterface{}. - Change the
nextpointer’s type from*LinkedListto*LinkedList[T]. When using a generic type, you must provide the type parameters. Leaving them out is a compile-time error.
Let's write some methods to work with our generic type. We'll start with a method to find the length of our linked list:
func (ll *LinkedList[T]) Len() int {
count := 0
for node := ll; node != nil; node = node.next {
count++
}
return count
}
return count
}
The method receiver uses *LinkedList[T] instead of *LinkedList, but the rest of the code is identical to the code that you'd write if you weren't using generics. Let's write a method that does refer to the parameterized type:
func (ll *LinkedList[T]) InsertAt(pos int, value T) *LinkedList[T] {
if ll == nil || pos <= 0 {
return &LinkedList[T]{
value: value,
next: ll,
}
}
ll.next = ll.next.InsertAt(pos-1, value)
return ll
}
This method takes in a parameter of type [T]
(This method isn’t the most efficient way to insert into a linked list, but it is short enough to make a good example. Also note that it is safe; if you pass 0 or a negative number for the insertion index, it will prepend to the linked list and if you pass a number greater than the length, it will simply append.)
Here are a few additional methods that are useful for our linked list:
func (ll *LinkedList(T)) Append(value T) *LinkedList(T) {
return ll.InsertAt(ll.Len(), value)
}
func (ll *LinkedList(T)) String() string {
if ll == nil {
return "nil"
}
return fmt.Sprintf("%v->%v", ll.value, ll.next.String())
}
And now that we have some useful methods on our generic type, let's try it out:
var head *LinkedList[string]
head = head.Append("Hello")
fmt.Println(head.String())
fmt.Println(head.Len())
head = head.Append("Hola")
head = head.Append("हैलो")
head = head.Append("こんにちは")
head = head.Append("你好")
fmt.Println(head.String())
fmt.Println(head.Len())
(We don’t need to call String explicitly when passing a value to fmt.Println, but I wanted to make it explicit. See https://tour.golang.org/methods/17 for more information.)
This looks exactly like existing Go code, with only one change: when declaring a variable of type *LinkedList, we supply the type that we want to use with this particular instance. This code prints out:
Hello->nil
1
Hello->Hola->हैलो->こんにちは->你好->nil
5
If we want to use our linked list with a different type, we simply supply the different type when we instantiate a different variable. If we have a type Person:
type Person struct {
Name string
Age int
}
We can write the following code:
var peopleList *LinkedList[Person]
peopleList = peopleList.Append(Person{"Fred", 23})
peopleList = peopleList.Append(Person{"Joan", 30})
fmt.Println(peopleList)
Which prints out:
{Fred 23}->{Joan 30}->nil
You can try out our linked list on The Go Playground at https://go.dev/play/p/ttsLLnRIs8M.
Let's try something new. We're going to add another method to our linked list to tell us whether or not a specific value is in it:
func (ll *LinkedList[T]) Contains(value T) bool {
for node := ll; node != nil; node = node.next {
if node.value == value {
return true
}
}
return false
}
Unfortunately, this will not work. If we try to compile it, we'll get the error:
```
invalid operation: node.value == value (type parameter T is not comparable with ==)
```
The problem is that our placeholder type T doesn't specify what it can do. So far, all we can do is store it and retrieve it. If we want to do more, we have to specify some constraints on T.
Since many (but not all!) Go types can be compared using == and !=, the Go generics proposal includes a new built-in interface called comparable. If we go back to the definition of our linked list type we can make a small change to support ==:
type LinkedList[type T comparable] struct {
value T
next *LinkedList[T]
}
We added the interface comparable to our type parameter definition clause and now we can use == to compare variables of type T within LinkedList's methods.
Using our previous data, if we run the following lines:
fmt.Println(head.Contains("Hello"))
fmt.Println(head.Contains("Goodbye"))
fmt.Println(peopleList.Contains(Person{"Joan", 30}))
You get the following results:
true
false
true
You can see this code run at https://go2goplay.golang.org/p/dO7npX6IeaQ.
However, we can no longer assign non-comparable types to LinkedList. If we tried to make a linked list of functions:
var functionList *LinkedList[func()]
functionList = functionList.Append(func() { fmt.Println("What about me?") })
fmt.Println(functionList)
It would fail at compilation time with the error message:
func() does not implement comparable
In addition to generic types, you can also write generic functions. One of the most common complaints about Go is that you cannot write a single function that processes a slice of any type. Let's write three:
func Map[type T, E](in []T, f func(T) E) []E {
out := make([]E, len(in))
for i, v := range in {
out[i] = f(v)
}
return out
}
func Reduce[type T, E](in []T, start E, f func(E, T) E) E {
out := start
for _, v := range in {
out = f(out, v)
}
return out
}
func Filter[type T](in []T, f func(T) bool) []T {
out := make([]T, 0, len(in))
for _, v := range in {
if f(v) {
out = append(out, v)
}
}
return out
}
Just like a generic type, a generic function has a type parameter section. For functions, it appears between the function name and the function parameters. For Map and Reduce, we are using two type parameters in our function, both declared in the type parameter section and separated by commas. The function bodies are identical to what you'd use if the types were specific; the only difference is that we pass []E to make in Map and []T to make in Filter.
When we run the code:
strings := []string{"1", "2", "Fred", "3"}
numStrings := Filter(strings, func(s string) bool {
_, err := strconv.Atoi(s)
return err == nil
})
fmt.Println(numStrings)
nums := Map(numStrings, func(s string) int {
val, _ := strconv.Atoi(s)
return val
})
fmt.Println(nums)
total := Reduce(nums, 0, func(start int, val int) int {
return start + val
})
fmt.Println(total)
We get the output:
1 2 3]
[1 2 3]
6
Try it for yourself at https://go2goplay.golang.org/p/ek3QTecbSL3.
One thing to notice: we didn't explicitly specify the types when invoking the functions. Go generics use type inference to figure which types to use for function calls. There are situations where this doesn't work (such as a type parameter that's used for a return type, but not an input parameter). In those cases, you are required to specify all of the type arguments.
Let's try to write another generic function. Go has a math.Max function that compares two float64 values and returns the larger one. It's written this way because nearly any other numeric type in Go can be converted to float64 for comparison (trivia time: a uint64 or int64 that requires more than 53 bits to express its value will lose precision when converted to a float64). Converting back and forth is ugly, so let's try to write a generic function to do this instead:
func Max(type T)(v1, v2 T) T {
if v1 > v2 {
return v1
}
return v2
}
Unfortunately, if we try to compile this function, we'll get an error:
cannot compare v1 > v2 (operator > not defined for T)
This is a lot like the error we got when we tried to compare values in our linked list, only this time it's the > operator instead of the ==. Go isn't going to provide a built-in interface to support other operators. In this case, we have to write our own interface using a _type list_:
type Ordered interface {
type string, int, int8, int16, int32, int64, float32, float64, uint, uint8, uint16, uint32, uintptr
}
func Max(type T Ordered)(v1, v2 T) T {
if v1 > v2 {
return v1
}
return v2
}
In order to work with operators, we declare an interface and list the types that support the operator that we want to use. Note that the valid operators are the ones that work for *all* of the listed types. For example, a generic function or type that uses Ordered as a type constraint cannot use - or *, because those are not defined for string.
Now that we have our interface constraint, we can pass an instance of any of those specified types (or any user-defined types whose underlying type is one of these types) into Max:
fmt.Println(Max(100, 200))
fmt.Println(Max(3.5, 1.2))
fmt.Println(Max("sheep", "goat"))
This produces the output:
200
3.5
sheep
You can try this for yourself at https://go.dev/play/p/_1OSnP87RSh .
By default, the type terms must match exactly. For example, say we had the code:
type MyInt int
var a MyInt = 10
var b MyInt = 20
fmt.Println(Max(a,b))
Our current definition of `Ordered` would cause the following compilation error:
```
MyInt does not implement Ordered (possibly missing ~ for int in constraint Ordered)
```
The error message hints at how to resolve this issue. If you want a type term to be an _underlying type_ (See the [Go language specification] for a definition), you need to prefix the type with `~`. If we change the definition of `Ordered` to:
```go
type Ordered interface {
~string | ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~float32 | ~float64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uintptr
}
```
Then our new code will compile and work correctly. You can try it on The Go Playground at: https://go.dev/play/p/ZoPPSP-EX3- .
Type terms provide a very concise way to specify what operators are available. They also allow you to specify what literals can be assigned to a variable of a generic type. Just as the available operators are the intersection of the operators on all types terms, the literals that can be assigned are the ones that can be assigned to all of the listed types. In the case of `Ordered`, you can't assign a literal, because there is no literal that can be assigned to both a `string` and any of the numeric types.
You can use any interface as a type constraint, not just comparable or one with a type list. And an interface used as a type constraint can contain both methods and a type list. However, you cannot use an interface with a type list as a regular interface type.
There is a lot more in generics than I can cover here. Read through the Go Generics Draft (formally called the Type Parameters - Draft Design) to see more details on the draft design, things that it doesn't cover, and additional sample code.
Generics vs. Interfaces
While it's very nice that Go reused the concept of interfaces to implement generics, it does lead to a little confusion. The question is: When do you use generics and when do you use interfaces?
Patterns for generics in Go are still being developed. There are some basic principles that are likely to be followed. The first principle is to do nothing. If your current code works with interfaces, leave it alone. Save generics for situations that can't be addressed with interfaces alone:
- If you have a container type, consider switching to generics when they are available. Save `interface{}` for situations where reflection is needed.
- If you had been writing multiple implementations of functions to handle different numeric types or slice types, switch to generics.
- If you want to write a function or method that creates a new instance, you need to use generics.
The next question that people ask is around performance. In the first release, the answer is: don't worry about it for now. Some things are faster when using generics and some are slower. The compiler is expected to improve over time, but chances are there won't be a significant difference for most programs.
What's Missing?
If you are a language geek, you're probably aware of other features that fall under the umbrella of generics in other languages. Many of them will probably be left out of Go's generics. These include:
- Specialization (Providing special-case implementations of a generic function for specific types).
- Metaprogramming (Code that generates code at compile time).
- Operator methods (Making a generic type that supports operators like `>`, `*`, or `[]`).
- Currying (Creating a new type or function based on a generic type by specifying some of the parameterized types).
What's Next?
It's still early days, but I'm excited about the prospects for this design. It adds the most requested features to Go without making the language a great deal more complicated. Some people will be disappointed that other advanced features are left out, but that’s not the Go way. Go is intended to be a simple language that’s easy to read, easy to learn, and easy to maintain. By adding just enough generics to solve the most common problems, Go continues to meet that ideal.
Pic by sustainableart on Freepik.com
