Rewriting a Go Library with v1.18 Generics
Go released generics with v1.18. Generics allow writing reusable functions and structures “templates” with types factored out. Without new generics support, users need to implement interface methods, e.g., sort, to use type agnostic libraries. In this article, we take a closer look at Go generics through an example transition on a Go data structure library and point out the differences and benefits.
Generics Heap
First, let’s look at the consumer side. The below code shows an earlier implementation that supports any type as an element of the Heap. Here, we are using the slice of interface{}, and we need to provide a comparison function to tell the library code how to order elements. Also, note the type assertions to int if we need to perform operations or call functions that take int after retrieving the elements as interface{}.
Below, we are using the new generics Heap[T]. Now, we can pass a slice of int directly; we do not need to provide a comparison function. Furthermore, since we are getting original types, there is no need for the extra step of type assertion either. The result is a much more fluent, intuitive, and clean way of using the library.
To make this happen, we used generics notation to templatize the interface and the factory functions. In addition, we limit the type constraints of the type for Heap[T] to be Ordered, by which it guarantees to support the operators <, <=, >=, >.
Custom comparison for user types
What if we want to use elements of custom types with custom comparison logic. Again, let’s look at the previous case. Here, we pass a comparison function for job struct type to order by priority field.
With HeapFlex[T] generics, we are adding a different constraint, Comparer[T], which enforces Compare method in the element type. We do not need any assertion as Extract returns job type and can directly access name and priority fields.
Implementation
We define two interfaces for users to pass in comparable types: one with Ordered constraint and the other with Comparer. We introduce an adapter implementation with a DefaultComparer wrapper, which relies on <, > operators. The underlying generics Heap is the same.
Another approach would be to limit the constraint to the Comparer interface and have only one Heap generics type. However, in that case, the users will have to implement the comparison for simple types, which will end up being similar to the interface{} approach we had before.
It would be more powerful if Go supports operator overloading so we could write one Heap implementation whether the underlying type is Ordered or a custom type that defines comparison operators. Operator overloading would enable a better library writing experience with a single implementation of data structures, reducing the complexity further.
Recap
We believe Go generics is an excellent addition to the language, enabling a cleaner consumer interface without sacrificing simplicity and type safety. Type constraints, and build time checks ensure correct type usage before execution. Above, we provided an example data structure showcasing Go generics. Some additional links to review: lib documentation, performance comparison, and the other rewritten data structures in the same library with Go generics.
References
