Statically typed generic data structures in Go
Apr 17, 2013
I gave a talk at the Go Boston meetup last night and figured I should write it up and put it here.
The second thing everyone says when they read up on Go is “There are no generics!”.
(The first thing people say is “There are no exceptions!”)
Both are only mostly true, but we’re only going to talk about generics today.
Go has generic built-in data structures - arrays, slices, maps, and channels. You just can’t create your own new type, and you can’t create generic functions. So, what’s a programmer to do? Find another language?
No. Many, possibly even most, problems can be solved with the built-in data structures. You can write pretty huge applications just using maps and slices and the occasional channel. There may be a tiny bit of code duplication, but probably not much, and certainly not any tricky code.
However, there definitely are times when you need more complicated data structures. Most people writing Go solve this problem by using Interface{}, the empty interface, which is basically like Object in C# or Java or void * in C/C++. It’s a thing that can hold any type… but then you need to type cast it to get at the actual type. This breaks static typing, since the compiler can’t tell if you make a mistake and pass the wrong type into something that takes an Interface{}, and it can’t tell until runtime if a cast will succeed or not.
So, is there any solution? Yes. The inspiration comes from the standard library’s sort package. Package sort can sort a slice of any type, it can even sort things that aren’t slices, if you’ve made your own custom data structure. How does it do that? To sort something, it must support the methods on sort.Interface. Most interesting is Less(i, j int). Less returns true if the item at index i in your data structure is Less than the object at index j in your data structure. Your code has to implement what “Less” means… and by only using indices, sort doesn’t need to know the types of objects held in your data structure.
This use of indices to blindly access data in a separate data structure is how we’ll implement our strongly typed tree. The tree structure will hold an index as its data value in each node, and the indices will index into a data structure that holds the actual objects. To make a tree of a new type, you simply implement a Compare function that the tree can use to compare the values at two indices in your data structure. You can use whatever data structure you like, probably a slice or a map, as long as you can use integers to reference values in the data structure.
In this way we separate the organization of the data from the storage of the data. The tree structure holds the organization, a slice or map (or something custom) stores the data. The indices are the generic pointers into the storage that holds the actual strongly typed values.
This does require a little code for each new tree type, just as using package sort requires a little code for each type. However, it’s only a few lines for a few functions, wrapping a tree and your data.
You can check out an example binary search tree I wrote that uses this technique in my github account
https://github.com/natefinch/tree
or go get the runnable sample tree:
go get github.com/natefinch/treesample
https://github.com/natefinch/tree
or go get the runnable sample tree:
go get github.com/natefinch/treesample
This required only 36 lines of code to make the actual tree structure (including empty lines and comments).
In some simple benchmarks, this implementation of a tree is about 25% faster than using the same code with Interface{} as the values and casting at runtime…. plus it’s strongly typed.