Generic interfaces: When to Use Them

There is an idea that is not obvious until you hear about it for the first time: as interfaces are types themselves, they too can have type parameters. This idea proves to be surprisingly powerful when it comes to expressing constraints on generic functions and types. In this post, we’ll demonstrate it, by discussing the use of interfaces with type parameters in a couple of common scenarios. A simple tree set As a motivating example, assume we need a generic version of a binary search tree. The elements stored in such a tree need to be ordered, so our type parameter needs a constraint that determines the ordering to use. A simple option is to use the cmp.Ordered constraint, introduced in Go 1.21. It restricts a type parameter to ordered types (strings and numbers) and allows methods of the type to use the built-in ordering operators. binary search tree cmp.Ordered // The zero value of a Tree is a ready-to-use empty tree. type Tree[E cmp.Ordered] struct { root *node[E] } func (t *Tree[E]) Insert(element E) { t.root = t.root.insert(element) } type node[E cmp.Ordered] struct { value E left *node[E] right *node[E] } func (n *node[E]) insert(element E) *node[E] { if n == nil { return &node[E]{value: element} } switch { case element n.value: n.right = n.right.insert(element) } return n } // The zero value of a Tree is a ready-to-use empty tree. type Tree[E cmp.Ordered] struct { root *node[E] } func (t *Tree[E]) Insert(element E) { t.root = t.root.insert(element) } type node[E cmp.Ordered] struct { value E left *node[E] right *node[E] } func (n *node[E]) insert(element E) *node[E] { if n == nil { return &node[E]{value: element} } switch { case element n.value: n.right = n.right.insert(element) } return n } (playground) playground However, this approach has the disadvantage that it only works on basic types for which < is defined; you cannot insert struct types, like time.Time. < time.Time We can remedy that by requiring the user to provide a comparison function: // A FuncTree must be created with NewFuncTree. type FuncTree[E any] struct { root *funcNode[E] cmp func(E, E) int } func NewFuncTree[E any](cmp func(E, E) int) *FuncTree[E] { return &FuncTree[E]{cmp: cmp} } func (t *FuncTree[E]) Insert(element E) { t.root = t.root.insert(t.cmp, element) } type funcNode[E any] struct { value E left *funcNode[E] right *funcNode[E] } func (n *funcNode[E]) insert(cmp func(E, E) int, element E) *funcNode[E] { if n == nil { return &funcNode[E]{value: element} } sign := cmp(element, n.value) switch { case sign 0: n.right = n.right.insert(cmp, element) } return n } // A FuncTree must be created with NewFuncTree. type FuncTree[E any] struct { root *funcNode[E] cmp func(E, E) int } func NewFuncTree[E any](cmp func(E, E) int) *FuncTree[E] { return &FuncTree[E]{cmp: cmp} } func (t *FuncTree[E]) Insert(element E) { t.root = t.root.insert(t.cmp, element) } type funcNode[E any] struct { value E left *funcNode[E] right *funcNode[E] } func (n *funcNode[E]) insert(cmp func(E, E) int, element E) *funcNode[E] { if n == nil { return &funcNode[E]{value: element} } sign := cmp(element, n.value) switch { case sign 0: n.right = n.right.insert(cmp, element) } return n } (playground) playground This works, but it also comes with downsides. We can no longer use the zero value of our container type, because it needs to have an explicitly initialized comparison function. And the use of a function field makes it harder for the compiler to inline the comparison calls, which can introduce a significant runtime overhead. Using a method on the element type can solve these issues, because methods are directly associated with a type. A method does not have to be explicitly passed and the compiler can see the target of the call and may be able to inline it. But how can we express the constraint to require that element types provide the necessary method? Using the receiver in constraints The first approach we might try is to define a plain old interface with a Compare method: Compare type Comparer interface { Compare(Comparer) int } type Comparer interface { Compare(Comparer) int } However, we quickly realize that this does not work well. To implement this interface, the method’s parameter must itself be Comparer. Not only does that mean that the implementation of this method must type-assert the parameter to its own type, it also requires that every type must explicitly refer to our package with the Comparer type by name (otherwise the method signatures would not be identical). That is not very orthogonal. Comparer Comparer A better approach is to make the Comparer interface itself generic: Comparer type Comparer[T any] interface { Compare(T) int } type Comparer[T any] interface { Compare(T) int } This Comparer now describes a whole family of interfaces, one for each type that Comparer may be instantiated with. A type that implements Comparer[T] declares “I can compare myself to a T”. For instance, time.Time naturally implements Comparer[time.Time] because it has a matching Compare method: Comparer Comparer Comparer[T] T time.Time Comparer[time.Time] it has a matching Compare // Implements Comparer[Time] func (t Time) Compare(u Time) int // Implements Comparer[Time] func (t Time) Compare(u Time) int This is better, but not enough. What we really want is a constraint that says that a type parameter can be compared to itself: we want the constraint to be self-referential. The subtle insight is that the self-referential aspect does not have to be part of the interface definition itself; specifically, the constraint for T in the Comparer type is just any. Instead, it is a consequence of how we use Comparer as a constraint for the type parameter of MethodTree: itself T Comparer any Comparer MethodTree // The zero value of a MethodTree is a ready-to-use empty tree. type MethodTree[E Comparer[E]] struct { root *methodNode[E] } func (t *MethodTree[E]) Insert(element E) { t.root = t.root.insert(element) } type methodNode[E Comparer[E]] struct { value E left *methodNode[E] right *methodNode[E] } func (n *methodNode[E]) insert(element E) *methodNode[E] { if n == nil { return &methodNode[E]{value: element} } sign := element.Compare(n.value) switch { case sign 0: n.right = n.right.insert(element) } return n } // The zero value of a MethodTree is a ready-to-use empty tree. type MethodTree[E Comparer[E]] struct { root *methodNode[E] } func (t *MethodTree[E]) Insert(element E) { t.root = t.root.insert(element) } type methodNode[E Comparer[E]] struct { value E left *methodNode[E] right *methodNode[E] } func (n *methodNode[E]) insert(element E) *methodNode[E] { if n == nil { return &methodNode[E]{value: element} } sign := element.Compare(n.value) switch { case sign 0: n.right = n.right.insert(element) } return n } (playground) playground Because time.Time implements Comparer[time.Time] it is now a valid type argument for this container, and we can still use the zero value as an empty container: time.Time Comparer[time.Time] var t MethodTree[time.Time] t.Insert(time.Now()) var t MethodTree[time.Time] t.Insert(time.Now()) For full flexibility, a library can provide all three API versions. If we want to minimize repetition, all versions could use a shared implementation. We could use the function version for that, as it is the most general: type node[E any] struct { value E left *node[E] right *node[E] } func (n *node[E]) insert(cmp func(E, E) int, element E) *node[E] { if n == nil { return &node[E]{value: element} } sign := cmp(element, n.value) switch { case sign 0: n.right = n.right.insert(cmp, element) } return n } // Insert inserts element into the tree, if E implements cmp.Ordered. func (t *Tree[E]) Insert(element E) { t.root = t.root.insert(cmp.Compare[E], element) } // Insert inserts element into the tree, using the provided comparison function. func (t *FuncTree[E]) Insert(element E) { t.root = t.root.insert(t.cmp, element) } // Insert inserts element into the tree, if E implements Comparer[E]. func (t *MethodTree[E]) Insert(element E) { t.root = t.root.insert(E.Compare, element) } type node[E any] struct { value E left *node[E] right *node[E] } func (n *node[E]) insert(cmp func(E, E) int, element E) *node[E] { if n == nil { return &node[E]{value: element} } sign := cmp(element, n.value) switch { case sign 0: n.right = n.right.insert(cmp, element) } return n } // Insert inserts element into the tree, if E implements cmp.Ordered. func (t *Tree[E]) Insert(element E) { t.root = t.root.insert(cmp.Compare[E], element) } // Insert inserts element into the tree, using the provided comparison function. func (t *FuncTree[E]) Insert(element E) { t.root = t.root.insert(t.cmp, element) } // Insert inserts element into the tree, if E implements Comparer[E]. func (t *MethodTree[E]) Insert(element E) { t.root = t.root.insert(E.Compare, element) } (playground) playground An important observation here is that the shared implementation (the function-based variant) is not constrained in any way. It must remain maximally flexible to serve as a common core. We also do not store the comparison function in a struct field. Instead, we pass it as a parameter because function arguments are easier for the compiler to analyze than struct fields. There is still some amount of boilerplate involved, of course. All the exported implementations need to replicate the full API with slightly different call patterns. But this part is straightforward to write and to read. Combining methods and type sets We can use our new tree data structure to implement an ordered set, providing element lookup in logarithmic time. Let’s now imagine we need to make lookup run in constant time; we might try to do this by maintaining an ordinary Go map alongside the tree: type OrderedSet[E Comparer[E]] struct { tree MethodTree[E] // for efficient iteration in order elements map[E]bool // for (near) constant time lookup } func (s *OrderedSet[E]) Has(e E) bool { return s.elements[e] } func (s *OrderedSet[E]) Insert(e E) { if s.elements == nil { s.elements = make(map[E]bool) } if s.elements[e] { return } s.elements[e] = true s.tree.Insert(e) } func (s *OrderedSet[E]) All() iter.Seq[E] { return func(yield func(E) bool) { s.tree.root.all(yield) } } func (n *node[E]) all(yield func(E) bool) bool { return n == nil || (n.left.all(yield) && yield(n.value) && n.right.all(yield)) } type OrderedSet[E Comparer[E]] struct { tree MethodTree[E] // for efficient iteration in order elements map[E]bool // for (near) constant time lookup } func (s *OrderedSet[E]) Has(e E) bool { return s.elements[e] } func (s *OrderedSet[E]) Insert(e E) { if s.elements == nil { s.elements = make(map[E]bool) } if s.elements[e] { return } s.elements[e] = true s.tree.Insert(e) } func (s *OrderedSet[E]) All() iter.Seq[E] { return func(yield func(E) bool) { s.tree.root.all(yield) } } func (n *node[E]) all(yield func(E) bool) bool { return n == nil || (n.left.all(yield) && yield(n.value) && n.right.all(yield)) } (playground) playground However, compiling this code will produce an error: invalid map key type E (missing comparable constraint) invalid map key type E (missing comparable constraint) The error message tells us that we need to further constrain our type parameter to be able to use it as a map key. The comparable constraint is a special predeclared constraint that is satisfied by all types for which the equality operators == and != are defined. In Go, that is also the set of types which can be used as keys for the built-in map type. comparable == != map We have three options to add this constraint to our type parameter, all with different tradeoffs: We can embed comparable into our original Comparer definition (playground): type Comparer[E any] interface { comparable Compare(E) int } This has the downside that it would also make our Tree types only usable with types that are comparable. In general, we do not want to unnecessarily restrict generic types. We can add a new constraint definition (playground). type Comparer[E any] interface { Compare(E) int } type ComparableComparer[E any] interface { comparable Comparer[E] } This is tidy, but it introduces a new identifier (ComparableComparer) into our API, and naming is hard. We can add the constraint inline into our more constrained type (playground): type OrderedSet[E interface { comparable Comparer[E] }] struct { tree Tree[E] elements map[E]struct{} } This can become a bit hard to read, especially if it needs to happen often. It also makes it harder to reuse the constraint in other places. We can embed comparable into our original Comparer definition (playground): type Comparer[E any] interface { comparable Compare(E) int } This has the downside that it would also make our Tree types only usable with types that are comparable. In general, we do not want to unnecessarily restrict generic types. We can embed comparable into our original Comparer definition (playground): embed comparable Comparer playground type Comparer[E any] interface { comparable Compare(E) int } type Comparer[E any] interface { comparable Compare(E) int } This has the downside that it would also make our Tree types only usable with types that are comparable. In general, we do not want to unnecessarily restrict generic types. Tree comparable We can add a new constraint definition (playground). type Comparer[E any] interface { Compare(E) int } type ComparableComparer[E any] interface { comparable Comparer[E] } This is tidy, but it introduces a new identifier (ComparableComparer) into our API, and naming is hard. We can add a new constraint definition (playground). playground type Comparer[E any] interface { Compare(E) int } type ComparableComparer[E any] interface { comparable Comparer[E] } type Comparer[E any] interface { Compare(E) int } type ComparableComparer[E any] interface { comparable Comparer[E] } This is tidy, but it introduces a new identifier (ComparableComparer) into our API, and naming is hard. ComparableComparer We can add the constraint inline into our more constrained type (playground): type OrderedSet[E interface { comparable Comparer[E] }] struct { tree Tree[E] elements map[E]struct{} } This can become a bit hard to read, especially if it needs to happen often. It also makes it harder to reuse the constraint in other places. We can add the constraint inline into our more constrained type (playground): playground type OrderedSet[E interface { comparable Comparer[E] }] struct { tree Tree[E] elements map[E]struct{} } type OrderedSet[E interface { comparable Comparer[E] }] struct { tree Tree[E] elements map[E]struct{} } This can become a bit hard to read, especially if it needs to happen often. It also makes it harder to reuse the constraint in other places. Which of these to use is a style choice and ultimately up to personal preference. (Not) constraining generic interfaces At this point it is worth discussing constraints on generic interfaces. You might want to define an interface for a generic container type. For example, say you have an algorithm that requires a set data structure. There are many different kinds of set implementations with different tradeoffs. Defining an interface for the set operations you require can add flexibility to your package, leaving the decision of what tradeoffs are right for the specific application to the user: type Set[E any] interface { Insert(E) Delete(E) Has(E) bool All() iter.Seq[E] } type Set[E any] interface { Insert(E) Delete(E) Has(E) bool All() iter.Seq[E] } A natural question here is what the constraint on this interface should be. If possible, type parameters on generic interfaces should use any as a constraint, allowing arbitrary types. any From our discussions above, the reasons should be clear: Different concrete implementations might require different constraints. All the Tree types we have examined above, as well as the OrderedSet type, can implement Set for their element types, even though these types have different constraints. Tree OrderedSet Set The point of defining an interface is to leave the implementation up to the user. Since one cannot predict what kinds of constraints a user may want to impose on their implementation, try to leave any constraints (stronger than any) to concrete implementations, not the interfaces. any Pointer receivers Let us try to use the Set interface in an example. Consider a function that removes duplicate elements in a sequence: Set // Unique removes duplicate elements from the input sequence, yielding only // the first instance of any element. func Unique[E comparable](input iter.Seq[E]) iter.Seq[E] { return func(yield func(E) bool) { seen := make(map[E]bool) for v := range input { if seen[v] { continue } if !yield(v) { return } seen[v] = true } } } // Unique removes duplicate elements from the input sequence, yielding only // the first instance of any element. func Unique[E comparable](input iter.Seq[E]) iter.Seq[E] { return func(yield func(E) bool) { seen := make(map[E]bool) for v := range input { if seen[v] { continue } if !yield(v) { return } seen[v] = true } } } (playground) playground This uses a map[E]bool as a simple set of E elements. Consequently, it works only for types that are comparable and which therefore define the built-in equality operators. If we want to generalize this to arbitrary types, we need to replace that with a generic set: map[E]bool E comparable // Unique removes duplicate elements from the input sequence, yielding only // the first instance of any element. func Unique[E any](input iter.Seq[E]) iter.Seq[E] { return func(yield func(E) bool) { var seen Set[E] for v := range input { if seen.Has(v) { continue } if !yield(v) { return } seen.Insert(v) } } } // Unique removes duplicate elements from the input sequence, yielding only // the first instance of any element. func Unique[E any](input iter.Seq[E]) iter.Seq[E] { return func(yield func(E) bool) { var seen Set[E] for v := range input { if seen.Has(v) { continue } if !yield(v) { return } seen.Insert(v) } } } (playground) playground However, this does not work. Set[E] is an interface type, and the seen variable will be initialized to nil. We need to use a concrete implementation of the Set[E] interface. But as we have seen in this post, there is no general implementation of a set that works for any element type. Set[E] seen nil Set[E] any We have to ask the user to provide a concrete implementation we can use, as an extra type parameter: // Unique removes duplicate elements from the input sequence, yielding only // the first instance of any element. func Unique[E any, S Set[E]](input iter.Seq[E]) iter.Seq[E] { return func(yield func(E) bool) { var seen S for v := range input { if seen.Has(v) { continue } if !yield(v) { return } seen.Insert(v) } } } // Unique removes duplicate elements from the input sequence, yielding only // the first instance of any element. func Unique[E any, S Set[E]](input iter.Seq[E]) iter.Seq[E] { return func(yield func(E) bool) { var seen S for v := range input { if seen.Has(v) { continue } if !yield(v) { return } seen.Insert(v) } } } (playground) playground However, if we instantiate this with our set implementation, we run into another problem: // OrderedSet[E] does not satisfy Set[E] (method All has pointer receiver) Unique[E, OrderedSet[E]](slices.Values(s)) // panic: invalid memory address or nil pointer dereference Unique[E, *OrderedSet[E]](slices.Values(s)) // OrderedSet[E] does not satisfy Set[E] (method All has pointer receiver) Unique[E, OrderedSet[E]](slices.Values(s)) // panic: invalid memory address or nil pointer dereference Unique[E, *OrderedSet[E]](slices.Values(s)) The first problem is clear from the error message: Our type constraint says that the type argument for S needs to implement the Set[E] interface. And as the methods on OrderedSet use a pointer receiver, the type argument also has to be the pointer type. S Set[E] OrderedSet When trying to do that, we run into the second problem. This stems from the fact that we declare a variable in the implementation: var seen S var seen S If S is *OrderedSet[E], the variable is initialized with nil, as before. Calling seen.Insert panics. S *OrderedSet[E] nil seen.Insert If we only have the pointer type, we cannot get a valid variable of the value type. And if we only have the value type, we cannot call pointer-methods on it. The consequence is that we need both the value and the pointer type. So we have to introduce an additional type parameter PS with a new constraint PtrToSet: and PS PtrToSet // PtrToSet is implemented by a pointer type implementing the Set[E] interface. type PtrToSet[S, E any] interface { *S Set[E] } // Unique removes duplicate elements from the input sequence, yielding only // the first instance of any element. func Unique[E, S any, PS PtrToSet[S, E]](input iter.Seq[E]) iter.Seq[E] { return func(yield func(E) bool) { // We convert to PS, as only that is constrained to have the methods. // The conversion is allowed, because the type set of PS only contains *S. seen := PS(new(S)) for v := range input { if seen.Has(v) { continue } if !yield(v) { return } seen.Insert(v) } } } // PtrToSet is implemented by a pointer type implementing the Set[E] interface. type PtrToSet[S, E any] interface { *S Set[E] } // Unique removes duplicate elements from the input sequence, yielding only // the first instance of any element. func Unique[E, S any, PS PtrToSet[S, E]](input iter.Seq[E]) iter.Seq[E] { return func(yield func(E) bool) { // We convert to PS, as only that is constrained to have the methods. // The conversion is allowed, because the type set of PS only contains *S. seen := PS(new(S)) for v := range input { if seen.Has(v) { continue } if !yield(v) { return } seen.Insert(v) } } } (playground) playground The trick here is the connection of the two type parameters in the function signature via the extra type parameter on the PtrToSet interface. S itself is unconstrained, but PS must have type *S and it must have the methods we need. So effectively, we are restricting S to have some methods, but those methods need to use a pointer receiver. PtrToSet S PS *S S While the definition of a function with this kind of constraint requires an additional type parameter, importantly this does not complicate code using it: as long as this extra type parameter is at the end of the type parameter list, it can be inferred: can be inferred // The third type argument is inferred to be *OrderedSet[int] Unique[int, OrderedSet[int]](slices.Values(s)) // The third type argument is inferred to be *OrderedSet[int] Unique[int, OrderedSet[int]](slices.Values(s)) This is a general pattern, and worth remembering: for when you encounter it in someone else’s work, or when you want to use it in your own. func SomeFunction[T any, PT interface{ *T; SomeMethods }]() func SomeFunction[T any, PT interface{ *T; SomeMethods }]() If you have two type parameters, where one is constrained to be a pointer to the other, the constraint ensures that the relevant methods use a pointer receiver. Should you constrain to pointer receivers? At this point, you might feel pretty overwhelmed. This is rather complicated and it seems unreasonable to expect every Go programmer to understand what is going on in this function signature. We also had to introduce yet more names into our API. When people cautioned against adding generics to Go in the first place, this is one of the things they were worried about. So if you find yourself entangled in these problems, it is worth taking a step back. We can often avoid this complexity by thinking about our problem in a different way. In this example, we built a function that takes an iter.Seq[E] and returns an iter.Seq[E] with the unique elements. But to do the deduplication, we needed to collect the unique elements into a set. And as this requires us to allocate the space for the entire result, we do not really benefit from representing the result as a stream. iter.Seq[E] iter.Seq[E] If we rethink this problem, we can avoid the extra type parameter altogether by using Set[E] as a regular interface value: Set[E] // InsertAll adds all unique elements from seq into set. func InsertAll[E any](set Set[E], seq iter.Seq[E]) { for v := range seq { set.Insert(v) } } // InsertAll adds all unique elements from seq into set. func InsertAll[E any](set Set[E], seq iter.Seq[E]) { for v := range seq { set.Insert(v) } } (playground) playground By using Set as a plain interface type, it is clear that the caller has to provide a valid value of their concrete implementation. This is a very common pattern. And if they need an iter.Seq[E], they can simply call All() on the set to obtain one. Set iter.Seq[E] All() set This complicates things for callers slightly, but it has another advantage over the constraint to pointer receivers: remember that we started with a map[E]bool as a simple set type. It is easy to implement the Set[E] interface on that basis: map[E]bool Set[E] type HashSet[E comparable] map[E]bool func (s HashSet[E]) Insert(v E) { s[v] = true } func (s HashSet[E]) Delete(v E) { delete(s, v) } func (s HashSet[E]) Has(v E) bool { return s[v] } func (s HashSet[E]) All() iter.Seq[E] { return maps.Keys(s) } type HashSet[E comparable] map[E]bool func (s HashSet[E]) Insert(v E) { s[v] = true } func (s HashSet[E]) Delete(v E) { delete(s, v) } func (s HashSet[E]) Has(v E) bool { return s[v] } func (s HashSet[E]) All() iter.Seq[E] { return maps.Keys(s) } (playground) playground This implementation does not use pointer receivers. So while this is perfectly valid, it would not be usable with the complicated constraint to pointer receivers. But it works fine with our InsertAll version. As with many constraints, enforcing that methods use a pointer receiver might actually be overly restrictive for many practical use cases. InsertAll Conclusion I hope this illustrates some of the patterns and trade-offs that type parameters on interfaces enable. It is a powerful tool, but it also comes with a cost. The primary take-aways are: Use generic interfaces to express constraints on the receiver by using them self-referentially. Use them to create constrained relationships between different type parameters. Use them to abstract over different implementations with different kinds of constraints. When you find yourself in a situation where you need to constrain to pointer receivers, consider whether you can refactor your code to avoid the extra complexity. See “Should you constrain to pointer receivers?” Use generic interfaces to express constraints on the receiver by using them self-referentially. Use them to create constrained relationships between different type parameters. Use them to abstract over different implementations with different kinds of constraints. When you find yourself in a situation where you need to constrain to pointer receivers, consider whether you can refactor your code to avoid the extra complexity. See “Should you constrain to pointer receivers?” “Should you constrain to pointer receivers?” As always, do not over-engineer things: a less flexible but simpler and more readable solution may ultimately be the wiser choice. Axel Wagner Axel Wagner This article is available on The Go Blog under a CC BY 4.0 DEED license. This article is available on The Go Blog under a CC BY 4.0 DEED license. The Go Blog The Go Blog Photo by Egor Komarov on Unsplash Photo by Egor Komarov on Unsplash Egor Komarov Unsplash