The joy of (type) sets

From Know Go

A set is a Many that allows itself to be thought of as a One.
—Georg Cantor, quoted in Rudy Rucker’s “Infinity and the Mind”

Let’s talk about sets, baby. The point of generic programming, as we’ve learned in this series, is to be able to write code that operates on more than one concrete data type. That way, we don’t have to repeat the same code over and over, once for each kind of data that we need it to handle.

But being free and easy about your data types can go too far: type parameters that accept literally any kind of data aren’t that useful. We need constraints to reduce the set of types that a function can deal with. When the type set is infinite (as it is with [T any], for example), then there’s almost nothing we can do with those values, because we’re infinitely ignorant about them.

So, how can we write more flexible constraints, whose type sets are broad enough to be useful, but narrow enough to be usable?

We already know that one way an interface can specify an allowed range of types is by listing method elements, such as String() string. We’ll use the term basic interface to describe interfaces like these that contain only method elements, but now let’s introduce another kind of interface. Instead of listing methods that the type must have, it directly specifies the set of types that are allowed.

Type elements

For example, suppose we wanted to write some generic function Double that multiplies a number by two, and we want a type constraint that allows only values of type int. We know that int has no methods, so we can’t use any basic interface as a constraint. How can we write it, then?

Well, here’s how:

type OnlyInt interface {
    int
}

Very straightforward! It looks just like a regular interface definition, except that instead of method elements, it contains a single type element, consisting of a named type. In this case, the named type is int.

Using a type set constraint

How would we use a constraint like this? Let’s write Double, then:

func Double[T OnlyInt](v T) T {
    return v * 2
}

In other words, for some T that satisfies the constraint OnlyInt, Double takes a T parameter and returns a T result.

Note that we now have one answer to the sort of problem we encountered when trying to write an AddAnything function: how to enable the * operator (or any other arithmetic operator) in a parameterised function. Since T can only be int (thanks to the OnlyInt constraint), Go can guarantee that the * operator will work with T values.

It’s not the complete answer, though, since there are other types that support * that wouldn’t be allowed by this constraint. And in any case, if we were only going to support int, we could have just written an ordinary function that took an int parameter.

So we’ll need to be able to expand the range of types allowed by our constraint a little, but not beyond the types that support *. How can we do that?

Unions

What types can satisfy the constraint OnlyInt? Well, only int! To broaden this range, we can create a constraint specifying more than one named type:

type Integer interface {
    int | int8 | int16 | int32 | int64
}

The types are separated by the pipe character, |. You can think of this as representing “or”. In other words, a type will satisfy this constraint if it is int or int8 or… you get the idea.

This kind of interface element is called a union. The type elements in a union can include any Go types, including interface types.

It can even include other constraints. In other words, we can compose new constraints from existing ones, like this:

type Float interface {
    float32 | float64
}

type Complex interface {
    complex64 | complex128
}

type Number interface {
    Integer | Float | Complex
}

We’re saying that Integer, Float, and Complex are all unions of different built-in numeric types, but we’re also creating a new constraint Number, which is a union of those three interface types we just defined. If it’s an integer, a float, or a complex number, then it’s a number!

The set of all allowed types

The type set of a constraint is the set of all types that satisfy it. The type set of the empty interface (any) is the set of all types, as you’d expect.

The type set of a union element (such as Float in the previous example) is the union of the type sets of all its terms.

In the Float example, which is the union of float32 | float64, its type set contains float32, float64, and no other types.

Intersections

You probably know that with a basic interface, a type must have all of the methods listed in order to implement the interface. And if the interface contains other interfaces, a type must implement all of those interfaces, not just one of them.

For example:

type ReaderStringer interface {
    io.Reader
    fmt.Stringer
}

If we were to write this as an interface literal, we would separate the methods with a semicolon instead of a newline, but the meaning is the same:

interface { io.Reader; fmt.Stringer }

To implement this interface, a type has to implement both io.Reader and fmt.Stringer. Just one or the other isn’t good enough.

Each line of an interface definition like this, then, is treated as a distinct type element. The type set of the interface as a whole is the intersection of the type sets of all its elements. That is, only those types that all the elements have in common.

So putting interface elements on different lines has the effect of requiring a type to implement all those elements. We don’t need this kind of interface very often, but we can imagine cases where it might be necessary.

Empty type sets

You might be wondering about what happens if we define an interface whose type set is completely empty. That is, if there are no types that can satisfy the constraint.

Well, that could happen with an intersection of two type sets that have no elements in common. For example:

type Unpossible interface {
    int
    string
}

Clearly no type can be both int and string at the same time! Or, to put it another way, this interface’s type set is empty.

If we try to instantiate a function constrained by Unpossible, we’ll find, naturally enough, that it can’t be done:

cannot implement Unpossible (empty type set)

We probably wouldn’t do this on purpose, since an unsatisfiable constraint doesn’t seem that useful. But with more sophisticated interfaces, we might accidentally reduce the allowed type set to zero, and it’s helpful to know what this error message means so that we can fix the problem.

Composite type literals

A composite type is one that’s built up from other types. We saw some composite types in the previous tutorial, such as []E, which is a slice of some element type E.

But we’re not restricted to defined types with names. We can also construct new types on the fly, using a type literal: that is, literally writing out the type definition as part of the interface.

For example, this interface specifies a struct type literal:

type Pointish interface {
    struct{ X, Y int }
}

A type parameter with this constraint would allow any instance of such a struct. In other words, its type set contains exactly one type: struct{ X, Y int }.

Access to struct fields

While we can write a generic function constrained by some struct type such as Pointish, there are limitations on what that function can do with that type. One is that it can’t access the struct’s fields:

func GetX[T Pointish](p T) int {
    return p.X
}
// p.X undefined (type T has no field or method X)

In other words, we can’t refer to a field on p, even though the function’s constraint explicitly says that any p is guaranteed to be a struct with at least the field X. This is a limitation of the Go compiler that has not yet been overcome. Sorry about that.

Some limitations of type sets

An interface containing type elements can only be used as a constraint on a type parameter. It can’t be used as the type of a variable or parameter declaration, like a basic interface can. That too is something that might change in the future, but this is where we are today.

What exactly stops us from doing that, though? We already know that we can write functions that take ordinary parameters of some basic interface type such as Stringer. So what happens if we try to do the same with an interface containing type elements, such as Number?

Let’s see:

func Double(p Number) Number {
// interface contains type constraints

This doesn’t compile, for the reasons we’ve discussed. Some potential confusion arises from the fact that a basic interface can be used as both a regular interface type and a constraint on type parameters. But interfaces that contain type elements can only be used as constraints.

Constraints are not classes

If you have some experience with languages that have classes (hierarchies of types), then there’s another thing that might trip you up with Go generics: constraints are not classes, and you can’t instantiate a generic function or type on a constraint interface.

To illustrate, suppose we have some concrete types Cow and Chicken:

type Cow struct{ moo string }

type Chicken struct{ cluck string }

And suppose we define some interface Animal whose type set consists of Cow and Chicken:

type Animal interface {
    Cow | Chicken
}

So far, so good, and suppose we now define a generic type Farm as a slice of T Animal:

type Farm[T Animal] []T

Since we know the type set of Animal contains exactly Cow and Chicken, then either of those types can be used to instantiate Farm:

dairy := Farm[Cow]{}
poultry := Farm[Chicken]{}

What about Animal itself? Could we create a Farm[Animal]? No, because there’s no such type as Animal. It’s a type constraint, not a type, so this gives an error:

mixed := Farm[Animal]{}
// interface contains type constraints

And, as we’ve seen, we also couldn’t use Animal as the type of some variable, or ordinary function parameter. Only basic interfaces can be used this way, not interfaces containing type elements.

Well, that’s it for this series. Thanks for sticking around. The addition of generics and iterators to Go has opened up a really exciting new world of programming, and my book Know Go is your complete guide to it. If you’ve enjoyed reading these excerpts, do consider buying the book. And if you’d like to truly master the craft of Go, you can study with me in person, one-to-one, through my mentoring programme.