(This developed from a thread with some other Cal Poly students discussing Go.)
One of the frequently asked questions about Go is why are there no generics in the language. It’s a fair point from the perspective of other OOP languages, but idiomatic Go code un-asks the question.
First, it is important to understand how interfaces work in Go. The gist is that interfaces use virtual method lookups, but retain the underlying type, so a conversion back to the original type is still type-safe. An empty interface (interface{}) works as a type-safe equivalent of C’s void*: you can put any type inside of an empty-interface variable, and then you can un-box it later.
The simplest way to define a linked list is through the empty interface: interface{}.
type Node struct {
Value interface{}
Next *Node
}
And indeed, this is how the container/list package package works, give or take some complexity. However, my argument is that this is the wrong way to do this. It requires an explicit boxing/un-boxing hit for every access, and this is where (I think) most of the call for generics comes from. There’s a much more idiomatic way to do this. My two case studies here are the sort package and the container/heap package from the standard library.
We start with sort, which defines an interface, sort.Interface:
package sort
func Sort(data Interface)
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less returns whether the element with index i should sort
// before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
This may not strike you as a generic container, but that is precisely the point. You can – with a bit of boilerplate – create a type that wraps a typed slice that implements sort.Interface. Thus, the algorithm can work on any type and only works uses indices. This is much cheaper than boxing/unboxing on access.
The second example is container/heap:
package heap
func Init(h Interface)
func Pop(h Interface) interface{}
func Push(h Interface, x interface{})
func Remove(h Interface, i int) interface{}
type Interface interface {
sort.Interface
Push(x interface{}) // add x as element Len()
Pop() interface{} // remove and return element Len() - 1.
}
Admittedly, there is a bit more boxing/un-boxing going on here, but the idea is still similar. We now have a data structure that requires very few box/unbox operations (two per push/pop). It is important to note that this is still type-safe.
You could implement a binary tree structure similarly:
package tree
func Search(root *Node, val interface{}) *Node
type Node struct {
Index int
Left, Right *Node
}
type Interface interface {
Len() int
Less(i, j int) bool
Push(x interface{})
Pop() interface{}
}
The Search function would push the val interface and use it for comparisons against the values stored in the tree, then pop it once finished. Admittedly, this isn’t the prettiest interface, but it works in a pinch. It works out to be only one box/un-box round-trip.
As we’ve seen, by “flipping” around the algorithms and separating them from the data structures using interfaces, we can still reap the benefits of generic containers from other languages.
