Using Go generics

About this post

Go version 1.18 includes generics. In this post, I will demonstrate an implementation of a binary tree data structure using generics.

I will not go into detail about generics. You can refer to these:

The generic binary tree

The example in this post will demonstrate the following aspects of generics.

Using an interface to specify generic constraints;
Implementing a generic binary tree via interfaces;
Using generic in the context of callbacks;
Constraint the binary tree to work with all Go numeric types.

Specifying a customer generic constraint types

I have created a generic type as a template for all Go numeric types. The code is as follows:

// NumericType is a generic type constrains consisting of Go numerics.
// NOTE: This is only for demonstration purpose only. There are a number
// of equivalent constraints in standard packages. One example is the
// `constraints` package. You can also use an alias to numeric constraints
// call `comparable`.
type NumericType interface {
	uint8 | uint16 | uint32 | uint64 | int8 | int16 | int32 | int64 | float32 | float64
}

Implementating the generic binary tree

In my demonstrator, I have separate the interface of my binary tree from its implementation code.

The interface of my binary tree looks like this:

// Node[N model.NumericType] of a binary tree
type Node[N model.NumericType] interface {

	// Key returns the node's key
	Key() N

	// Count the number of duplicate keys
	Count() uint32

	// AddCount to number of duplicate keys
	AddCount(count uint32)

	// Left return the left child
	Left() Node[N]

	// SetLeft child
	SetLeft(left Node[N])

	// Right returns the right child
	Right() Node[N]

	// SetRight right child
	SetRight(left Node[N])
}

In this case, I am using my customer generic type constraint NumericType specified in the package named model.

I have implemented my binary tree node based on the above interface this way:

// default implementation of a binary node using pointers.
// NOTE: This is not serializable.
type defaultNode[N model.NumericType] struct {
	key   N
	count uint32
	left  Node[N]
	right Node[N]
}

func (p *defaultNode[N]) Key() N {
	return p.key
}

func (d *defaultNode[N]) Count() uint32 {
	return d.count
}

func (d *defaultNode[N]) AddCount(count uint32) {
	d.count = count
}

func (p *defaultNode[N]) Left() Node[N] {
	return p.left
}

func (p *defaultNode[N]) SetLeft(left Node[N]) {
	p.left = left
}

func (p *defaultNode[N]) Right() Node[N] {
	return p.right
}

func (p *defaultNode[N]) SetRight(right Node[N]) {
	p.right = right
}

I have also created a default node builder like this:

// NewDefaultNode instantiate a reference to adefault implementation
// of a Node
func NewDefaultNode[N model.NumericType](key N) Node[N] {
	return &defaultNode[N]{
		key: key,
	}
}

This builder supports the creation of defaultNodes based on a range of numeric types.

I have also created a callback type NewNode to support multiple builder types which looks like this:

// NewNode[N model.NumericType] is a callback to an implementation to instantiate a node
type NewNode[N model.NumericType] func(key N) Node[N]

I can use this call back to inject to node builder to make my generic binary tree InsertNode operations able to deal with several implementations. The code for my tree insertion looks like this:

// InsertNode[N model.NumericType] an operation to insert a node in a binary tree.
func InsertNode[N model.NumericType](newNode NewNode[N], root Node[N], key N) Node[N] {

	if root == nil {
		root = newNode(key)
	}

	if root.Key() == key {
		root.AddCount(root.Count() + 1)
	}

	if root.Key() < key {
		root.SetRight(InsertNode(newNode, root.Right(), key))
	}

	if root.Key() > key {
		root.SetLeft(InsertNode(newNode, root.Left(), key))
	}

	return root
}

Using the generic binary tree

Go generics is not unlike generics found in other languages such as C++ template. To use a generic, you must first instantiate with the underlying type.

You can see an example demonstrating the steps in instantiating a uint8 node here:

func Example_insertNode1() {
	root := InsertNode(NewDefaultNode[uint8], nil, 6)

	root = InsertNode(NewDefaultNode[uint8], root, 3)
	root = InsertNode(NewDefaultNode[uint8], root, 7)

	root = InsertNode(NewDefaultNode[uint8], root, 3)
	root = InsertNode(NewDefaultNode[uint8], root, 2)
	root = InsertNode(NewDefaultNode[uint8], root, 8)
	root = InsertNode(NewDefaultNode[uint8], root, 4)

	fmt.Printf("Level 0. Node: %v(%v)\n", root.Key(), root.Count())
	fmt.Printf("Level 1. Nodes: %v(%v) %v(%v)\n", root.Left().Key(), root.Left().Count(), root.Right().Key(), root.Right().Count())
	fmt.Printf("Level 2. Nodes: %v(%v) %v(%v) %v(nil) %v(%v)", root.Left().Left().Key(), root.Left().Left().Count(), root.Left().Right().Key(), root.Left().Right().Count(), root.Right().Left(), root.Right().Right().Key(), root.Right().Right().Count())

	// Output:
	// Level 0. Node: 6(1)
	// Level 1. Nodes: 3(2) 7(1)
	// Level 2. Nodes: 2(1) 4(1) <nil>(nil) 8(1)
}

You will notice a very useful feature of Go generic is the compiler ability to infer types being instantiated. For example the InsertNode operation does not require explicit declaration of the underlying type uint8. It can infer from the function arguments the underlying type. This feature reduce code verbosity.

In the case of the call back function NewDefaultNode, it was necessary to instantiate with a specific type as the compiler could not infer the underlying type. We can simply instantiate the function by declaring it this way NewDefaultNode[uint8].

My view of Go generics

Based on my experience building the demonstrator, I found the syntax for declaring and instantiating generic types very easy. Admittedly, I have had the experience of using generics in other languages. So I already had the foundation to exploit this Go feature.

However, I think anyone new to generics will find it easy to use this feature. The Go tooling will guide you by flagging potential errors at compile time, thus minimising errors at runtime. The challenge, which is not specific to Go, is deciding when it is appropriate to use generics.

Paul Sitoh