Generics are the Generics of Go

Go might soon include its most requested feature


About three 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 are about to change. The Go team has released a blog post and a draft spec that describe a potential implementation of generics for Go. The draft proposal uses parameterized types to add 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 today:

    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:

  1.  Place [type T] 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.
  2. Use T for the value field's type instead of interface{}.
  3. Change the next pointer’s type from *LinkedList to *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
  

Just as The Go Playground allows you to try out current Go code, the Go team has made a new playground for testing generic code. You can try out our linked list at https://go2goplay.golang.org/p/OUX5OKRMqQw

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:

    cannot compare node.value == value (operator == not defined for T)
  

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 satisfy 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://go2goplay.golang.org/p/PlQO-TFBZE9.

The types specified in a type list are underlying types. (See the Go language specification for a definition). That means the following code also works:

    type MyInt int

var a MyInt = 10
var b MyInt = 20
fmt.Println(Max(a,b))
  

To be honest, I don't prefer type lists. However, they 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 in the type list, 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 bit of confusion. The question is: When do you use generics and when do you use interfaces?

It's still very early days, so patterns 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:

  1. If you have a container type, consider switching to generics when they are available. Save `interface{}` for situations where reflection is needed.
  2. If you had been writing multiple implementations of functions to handle different numeric types or slice types, switch to generics.
  3. 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. The answer is: don't worry about it for now. The current prototype tools are using a technique (re-writing generic Go code to standard Go code) that isn't going to be used in any production release. There are multiple ways to compile and implement generics. Once there are final tools, we'll be able to see what the tradeoffs are. 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?

The generics design is still in the draft stage; it's likely that there will be further tweaks. If the design becomes a proposal and that proposal is accepted, the earliest possible release that would include generics is Go 1.17.

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


Jon Bodner, Distinguished Engineer - Open Source Program Office/Delivery Experience

Jon Bodner has been developing software professionally for nearly 20 years as a programmer, chief engineer, and architect. He has worked in a wide variety of industries: government, education, internet, legal, financial, and e-commerce. His work has taken him from the internals of the JVM to the DNS resolvers that shape internet traffic. A veteran of several startups, Jonathan was also the architect for Blackboard's Beyond division, which was the company's first foray into cloud services. He holds a BS in Computer Science from Rensselaer Polytechnic Institute and an MS in Computer Science from the University of Wisconsin-Madison. Jonathan lives in Rockville, Maryland with his wife and children.


DISCLOSURE STATEMENT: © 2020 Capital One. Opinions are those of the individual author. Unless noted otherwise in this post, Capital One is not affiliated with, nor endorsed by, any of the companies mentioned. All trademarks and other intellectual property used or displayed are property of their respective owners.

Related Content