Generic functions on slices with Go type parameters

Generic functions for slices?

Let's start by defining the problem; Ian Lance Taylor has an excellent talk and blog post called "Why Generics?" on the topic, and I highly recommend you watch/read that first.

I'll be using Ian's function to reverse slices as a motivating example, and will move quickly through the topics that are already covered in that talk.

Suppose we want to write a function to reverse a slice in Go; we can start with a concrete function to reverse a slice of ints :

func ReverseInts(s []int) {
  first := 0
  last := len(s) - 1
  for first < last {
    s[first], s[last] = s[last], s[first]
    first++
    last--
  }
}

How about reversing a slice of strings?

func ReverseStrings(s []string) {
  first := 0
  last := len(s) - 1
  for first < last {
    s[first], s[last] = s[last], s[first]
    first++
    last--
  }
}

Well, it looks exactly like the previous function, with a simple int->string substitution in the type. Can't we write this function only once?

Go permits polymorphism via interfaces; let's try to write a "generic" function to reverse a slice of any type:

func ReverseAnything(s []interface{}) {
  first := 0
  last := len(s) - 1
  for first < last {
    s[first], s[last] = s[last], s[first]
    first++
    last--
  }
}

We can call it as follows, and it works as expected:

iints := []interface{}{2, 3, 4, 5}
ReverseAnything(iints)

istrings := []interface{}{"joe", "mike", "hello"}
ReverseAnything(istrings)

So wait, is this it? Go has had generics all along? Not quite. While ReverseAnything will dutifilly reverse a slice of interface{}, we don't typically hold data in such slices in Go. We could do it, theoretically, but that would forego much of Go's static typing, relying on (runtime) type assertions at every turn [1]

It would all work great if we could just pass our []int into ReverseAnything; but that's not possible, for a variety of good reasons.

We could also copy our []int into a []interface{} prior to reversing it, but this carries significant disadvantages:

1. Much more code: instead of reversing a slice, we have to copy our slice into a []interface{}, then call the reverse function, then copy the result back into a []int.
2. Efficiency hit - lots of copying data arround and allocations of new slices, whereas a simple call to ReverseInts(intslice) is a single loop with no unnecessary copies and zero allocations.

There are other approaches we could take, like code generation, but these have different issues that make them cumbersome.

This is where the type parameters proposal comes in.

Writing generic code with type parameters

Using the type parameters proposal, writing a generic slice reversal function is simple:

func ReverseSlice[T any](s []T) {
  first := 0
  last := len(s) - 1
  for first < last {
    s[first], s[last] = s[last], s[first]
    first++
    last--
  }
}

The square bracket region following the function's name defines a type parameter for the function's use. [T any] means that T is a type parameter that can be any type. Not surprisingly, the body of the function remains exactly the same as in our non-generic versions.

Here's how we use it:

s := []int{2, 4, 8, 11}
ReverseSlice(s)

ss := []string{"joe", "mike", "hello"}
ReverseSlice(ss)

Due to type inference, we don't have to specify the type parameters when we invoke ReverseSlice in this case (and in the vast majority of other cases, actually); it "just works".

I won't go into details about how the compiler accomplishes this, because the implementation details are still in flux. Moreover, different Go compilers may choose to implement this differently, and that's fine.

I will highlight one important aspect of the proposal, however: values of type parameters are not boxed. This has significant implications for efficiency! It means that whatever overhead generic functions add (in terms of run time and memory footprint), it's likely to be a constant overhead that's not a function of the slice's size.

More examples of generic slice functions

Type parameters finally allow programmers to write generic functions like map, reduce and filter! Whether you think such functions are a good stylistic fit to Go or not, they are a good demonstration of the capabilities of this new functionality in Go. Let's take map, for example:

func Map[T, U any](s []T, f func(T) U) []U {
  r := make([]U, len(s))
  for i, v := range s {
    r[i] = f(v)
  }
  return r
}

It's parameterized by two types - one for the slice element, one for the returned slice element. Here's a hypothetical usage scenario:

s := []int{2, 4, 8, 11}
ds := Map(s, func(i int) string {return strconv.Itoa(2*i)})

The mapping function takes an int and returns a string. This is enough for Go's type inference to understand that T is int and U is string in the call to Map, and we don't have to specify any types explicitly. ds is inferred to be []string.

Naturally, we could also use Map with existing functions from the standard library, e.g.:

names := []string{"joe", "mike", "sue"}
namesUpper := Map(names, strings.ToUpper)

Here's Filter:

func Filter[T any](s []T, f func(T) bool) []T {
  var r []T
  for _, v := range s {
    if f(v) {
      r = append(r, v)
    }
  }
  return r
}

We would use it as follows:

evens := Filter(s, func(i int) bool {return i % 2 == 0})

Finally, here's Reduce:

func Reduce[T, U any](s []T, init U, f func(U, T) U) U {
  r := init
  for _, v := range s {
    r = f(r, v)
  }
  return r
}

And sample usage:

product := Reduce(s, 1, func(a, b int) int {return a*b})

Trying type parameters today

Even though generics will not be available in Go before 1.18, you can play with them today and try all the code I pasted in this post (and whatever else strikes your fancy). There are a couple of ways.

The easiest way to try small snippets is on the go2go version of the Go Playground. It's kept reasonably in sync with the type parameters development branch of the Go toolchain.

To be on the bleeding edge and/or to write more substantial pieces of code, you can:

1. Clone the Go repository (following these instructions).
2. Check out the dev.go2go branch.
3. Build the toolchain (also detailed in the link in step 1)
4. Use go tool go2go to run code samples.

In the source repository accompanying this post, you'll find a simple bash script that set ups env vars properly to do step 4. Feel free to use it for your own needs.

Once you've cloned the repo and checked out the dev.go2go branch, take a look at the directory src/cmd/go2go/testdata/go2path/src. It contains many examples of generic Go code using type parameters that are very interesting to study.

Update (2021-10-30): Now that generics landed in the development branch of Go 1.18, you can use gotip to run generic code much more easily.

Update (2022-03-16): Go 1.18 has been released with support for generics. The code samples in this post should work on Go 1.18