Abhinav Gupta | About

Introduction to generics in Go

Go 1.18 added support for a long awaited feature: type parameterization — also referred to as generics. This article provides a short walk-through of the feature.

1. Motivation

As a motivating example, let’s start with a function that takes a slice of integers and removes duplicate values from it.

// UniqueInts removes duplicate integers from a slice
// and returns the new slice.
// The original slice is unusable after this operation runs.
func UniqueInts(items []int) []int {
  newItems := items[:0]
  seen := make(map[int]struct{})
  for _, item := range items {
    if _, ok := seen[item]; !ok {
      newItems = append(newItems, item)
      seen[item] = struct{}{}
    }
  }
  return newItems
}
💡 Tip
 The snippet above uses a standard pattern to filter the slice without creating a new one. See Filter Go slices without allocating if this pattern is new to you.

This function is used like so:

items := []int{1, 2, 3, 1, 4, 2, 5, 3, 6}
items = UniqueInts(items)
// [1 2 3 4 5 6]

Take a step back and consider the core logic of the function:

seen := make(map[int]struct{}) (1)
for _, item := range items {   (2)
  if _, ok := seen[item]; !ok { (3)
    newItems = append(newItems, item) (4)
    seen[item] = struct{}{}           (5)
  }
}

  1. Create a map to track items we’ve seen.

  2. For each item in the original slice…​

  3. …​if we haven’t already seen the item…​

  4. …​add the item to the new slice…​

  5. …​and mark it as seen.

There’s nothing int-specific about this except it references int. We can copy-and-paste the same code, swap out the int for string, and get a UniqueStrings function.

  • Diff

  • Result

-func UniqueInts(items []int) []int {
+func UniqueStrings(items []string) []string {
  newItems := items[:0]
- seen := make(map[int]struct{})
+ seen := make(map[string]struct{})
  for _, item := range items {
    if _, ok := seen[item]; !ok {
      newItems = append(newItems, item)
      seen[item] = struct{}{}
    }
  }
  return newItems
 }
func UniqueStrings(items []string) []string {
  newItems := items[:0]
  seen := make(map[string]struct{})
  for _, item := range items {
    if _, ok := seen[item]; !ok {
      newItems = append(newItems, item)
      seen[item] = struct{}{}
    }
  }
  return newItems
}

However, instead of trying to anticipate every type we need this function for, generics allow us to generalize this function so that it works with any type usable as a map key.

2. Generic functions

Let’s generalize the function to any type that can be used as a map key. Make the following change, and leave the rest of the function as-is.

  • Diff

  • Result

-func UniqueInts(items []int) []int {
+func Unique[T comparable](items []T) []T {
  newItems := items[:0]
- seen := make(map[int]struct{})
+ seen := make(map[T]struct{})
  for _, item := range items {
    if _, ok := seen[item]; !ok {
      newItems = append(newItems, item)
      seen[item] = struct{}{}
    }
  }
  return newItems
 }
func Unique[T comparable](items []T) []T {
  newItems := items[:0]
  seen := make(map[T]struct{})
  for _, item := range items {
    if _, ok := seen[item]; !ok {
      newItems = append(newItems, item)
      seen[item] = struct{}{}
    }
  }
  return newItems
}

There’s some new syntax here:

func Unique[T comparable](items []T) []T

The […​] next to the function defines the type parameters expected by the function and the constraints they must satisfy — as opposed to (…​) which defines value parameters and their types.

[…​]

type parameter

constraint

(…​)

value parameter

type

So read [T comparable] as, "T is a type that satisfies the comparable constraint." This constraint allows us to write code that uses T as a map key.

You can use the new version of Unique like so:

fmt.Println(Unique[int]([]int{1, 2, 3, 1, 4, 2, 5, 3, 6}))
// [1 2 3 4 5 6]

fmt.Println(Unique[string]([]string{"foo", "bar", "foo", "baz"}))
// [foo bar baz]

In many cases — like this one — you can omit some or all of the type parameters if the Go type system can infer them from the value parameters.

fmt.Println(Unique([]int{1, 2, 3, 1, 4, 2, 5, 3, 6}))
// [1 2 3 4 5 6]

fmt.Println(Unique([]string{"foo", "bar", "foo", "baz"}))
// [foo bar baz]

3. Generic types

Let’s build upon this. Instead of making a slice unique after the fact, we’d like to keep a collection of unique items — a set.

Before generics we would pass a map[T]struct{} around for different kinds of sets we need in our code. With generics we can build a Set[T] type and leave the map as an implementation detail. Let’s do that.

Declare a Set with a T comparable type parameter. Inside it, declare a map[T]struct{} field.

type Set[T comparable] struct {
  items map[T]struct{}
}

Set[T comparable] is new syntax, but it’s similar to the previously used func Unique[T comparable](…​). It declares a new type Set parameterized over any type T that satisfies the comparable constraint.

Add a constructor for Set[T].

func NewSet[T comparable]() *Set[T] {
  return &Set[T]{
    items: make(map[T]struct{}),
  }
}

Why are we repeating [T comparable]?

Looking at the snippet above, you might wonder about the [T comparable]. We already specified that for type Set[…​]. Why do we have to repeat it again?

We have to repeat it because NewSet is not actually a method. Go has no language-level concept of constructors. NewSet is just a generic top-level function that happens to return a Set[T].

We won’t have to repeat ourselves for methods of Set[T].

Let’s add a few methods:

  • Put places items into the set:

    func (s *Set[T]) Put(item T) {
  s.items[item] = struct{}{}
}

  • Has checks if something exists in it:

    func (s *Set[T]) Has(item T) bool {
  _, ok := s.items[item]
  return ok
}

  • Items returns a slice of items in the set:

    func (s *Set[T]) Items() []T {
  items := make([]T, 0, len(s.items))
  for item := range s.items {
    items = append(items, item)
  }
  return items
}

They may be used like so:

ints := NewSet[int]()
ints.Put(1)
ints.Put(2)
ints.Put(1)

fmt.Println(ints.Has(1)) // true
fmt.Println(ints.Has(2)) // true
fmt.Println(ints.Has(3)) // false

fmt.Println(ints.Items()) // [1 2] or [2 1] (1)

  1. Items works by iterating over the map[T]struct{}. In Go, the iteration order of a map is indeterminate, so we cannot make guarantees about the order of items in the slice.

3.1. Transformation

Suppose we have a Set[int] and we need to build a Set[string] from it. The Go standard library includes strconv.Itoa to turn an integer to a string.

package strconv

func Itoa(i int) string

It would be nice if we could do something like this:

strs := ints.Transform(func(i int) string {
  return strconv.Itoa(i)
})
fmt.Println(strs.Has("1")) // true

Let’s try to implement this:

func (s *Set[T]) Transform[V comparable](fn func(T) V) *Set[V] { (1)
  vs := NewSet[V]()
  for item := range s.items {
    vs.Put(fn(item))
  }
  return vs
}

  1. The new method declares a new type parameter V, expects a function that takes a T and returns a V, applies that function to every element in the set, and returns a Set[V].

Compile it, and we’ll see.

syntax error: method must have no type parameters

That didn’t work. As of writing this, generics in Go do not support type parameters on methods. Methods can be generic only over the type parameters that the associated type defined for itself.

What does this limitation mean for Transform? We can’t implement Transform as a method. We can still implement it as a top-level function.

Design around it

Turn the Transform method into a function and merge the type and value parameters. Everything else remains the same.

  • Diff

  • Result

-func (s *Set[T]) Transform[V comparable](fn func(T) V) *Set[V] {
+func Transform[T, V comparable](s *Set[T], fn func(T) V) *Set[V] {
  vs := NewSet[V]()
  for item := range s.items {
    vs.Put(fn(item))
  }
  return vs
 }
func Transform[T, V comparable](s *Set[T], fn func(T) V) *Set[V] {
  vs := NewSet[V]()
  for item := range s.items {
    vs.Put(fn(item))
  }
  return vs
}

Use it like so:

  strs := Transform(ints, func(i int) string {
    return strconv.Itoa(i)
  })
  fmt.Println(strs.Has("1")) // true
  fmt.Println(strs.Has("2")) // true
  fmt.Println(strs.Has("3")) // true

3.2. Specialized methods

Let’s look at the Set.Items method again:

func (s *Set[T]) Items() []T {
  items := make([]T, 0, len(s.items))
  for item := range s.items {
    items = append(items, item)
  }
  return items
}

This has a small annoyance in its behavior as noted earlier: there are no guarantees about the order of items in the returned slice because we build the slice by iterating through the map, and the iteration order over maps in Go is indeterminate.

It would be nice if we could have a SortedItems method that sorts these items if they can be sorted. Perhaps, we can use the constraints.Ordered constraint to determine if we can sort something, and sort the slice with slices.Sort.

Let’s try to implement this:

func (s *Set[T constraints.Ordered]) SortedItems() []T {
  items := s.Items()
  slices.Sort(items)
  return items
}

Compile it, and we’ll see.

syntax error: unexpected constraints, expecting ]

That didn’t work. Generics in Go do not support methods that exist only if other additional constraints are satisfied.

Okay, how about we turn it into a top-level function like the previous section?

Design around it

Turn the method into a top-level function, turning the receiver into a parameter:

  • Diff

  • Result

-func (s *Set[T constraints.Ordered]) SortedItems() []T {
+func SortedItems[T constraints.Ordered](s *Set[T]) []T {
  items := s.Items()
  slices.Sort(items)
  return items
 }
func SortedItems[T constraints.Ordered](s *Set[T]) []T {
  items := s.Items()
  slices.Sort(items)
  return items
}

This works now.

strs := Transform(ints, func(i int) string {
  return strconv.Itoa(i)
})

fmt.Println(SortedItems(strs)) // [1 2]

We can also declare a SortedItemsFunc function that accepts a custom comparison criteria with slices.SortFunc.

func SortedItemsFunc[T comparable](s *Set[T], less func(a, b T) bool) []T {
  items := s.Items()
  slices.SortFunc(items, less)
  return items
}

Example usage:

reverse := SortedItemsFunc(strs, func(a, b string) bool {
  return b < a
})
fmt.Println(reverse) // [2 1]

4. Conclusion

In summary, generics are a powerful feature. With them, you can build functions and types parameterized over other types. You can reduce copy-paste boilerplate in specific scenarios with them. They come with some limitations, but you can design around these limitations to some degree.

My recommendation for folks new to generics is this: use them when you need them, but don’t look for places to use them. Or, quoting Ian Lance Taylor:

write Go programs by writing code, not by defining types

— Ian Lance Taylor
When To Use Generics

Written on .