Order between objects is done by comparing them, but comparison is also used for equality check, which can have various meanings. Go is very strict about the comparison operators, and allows to use them only in a limited number of cases. Additionally, Go explicitly chose not to permit operator overloading (probably justifiably). As a consequence, defining order between objects generally requires defining an order function. This makes Go very safe, with a tradeoff on usability and readability. In this post, we’ll discuss orderings and comparisons in general, ordering approaches in Go, and how the order library can help.

I would love to know what you think. Please use the comments platform on the bottom of the post for discussion.

Two Types of Comparisons

The Go spec distinguishes between two comparison operator types:

• The equality operators ==, !=. Go allows applying them only on comparable operands.
• The ordering operators <, <=, > and >=. Go allows applying them only on ordered operands.

In Go, the different types can be comparable, ordered, both comparable and ordered, or none. For example bool is comparable but not ordered (true > false won’t compile), and func object can only be compared with nil (if f is a func, f == f won’t compile).

Go standard library provides the reflect.DeepEqual function, which is a “recursive relaxation of Go’s == operator” and allows checking equality for more complex objects than the == operator allows. Additionally, the go-cmp external package enables custom definition of comparison operations and diff output in case of inequality.

Go currently lacks advanced support for defining order.

Three-Way Comparison

Go’s strict comparison rules and absence of operator overloading, leave the programmer with the need to use methods and functions in order to define custom ordering. A common approach for ordering definition is the one taken by C’s strcmp and memcmp functions, which are three-way comparison functions. These functions are of the generic form func(T, T) int, and map the relation between two T values to the int space:

if a <  b then cmp(a, b) <  0
if a == b then cmp(a, b) == 0
if a >  b then cmp(a, b) >  0

Using the three-way comparison function might be harder to understand: reading cmp(a, b) < 0 is not translated immediately as a < b. One way to remember how to translate the reading of such comparison is with the following diff:

-a <op> b
+cmp(a, b) <op> 0

In Go standard library, there are the strings.Compare and bytes.Compare that are three-way comparison functions.

Comparing objects can be also done with methods. For example, the time package chose to implement time.Time comparison methods: time.Time.Equal, time.Time.After and time.Time.Before. This approach is a bit more readable - reading a.After(b) is very clear. However, in some cases it can be overwhelming - checking if a >= b is done by two function calls: a.After(b) || a.Equal(b).

The order package provides the order.By function that accepts a generic three-way comparison function, returns an order object:

import "github.com/posener/order"

// T is some type.
type T ...

// orderT defines the order of T objects using a three-way comparison function.
var orderT = order.By(func(a, b T) int { .... })

func main() {
	var a, b T
	if orderT.Is(a).GreaterEqual(b) { ... }
}

The order package also supports types which implement the generic order interface func (T) Compare(T) int:

// T is some type.
type T ...

// Compare defines the order of T objects.
func (t T) Compare(other T) int { .... }

func main() {
    var a, b T
    
    // order.Is, like all other functions in the order package can be used with objects that
    // implement the generic order interface.
	if order.Is(a).GreaterEqual(b) { ... }
}

Types

Let’s discuss the role of types in the two different comparison types. The Go spec defines that comparisons can be done only when a’s value is assignable to b’s type or b’s value to as type. This requirement makes Go’s code safe, and prevents developers from making easy mistakes:

• int32(1) != int64(1), or given type s string, "foo" != s("foo"). Even though the values are identical, comparing different types is compile time error. In this case, the developer should convert the types in a safe way before comparing them. For example, convert the int32 to int64 and not the other way around.
• Given a int, a != &a. Even though the content of a is identical, comparing a value to a pointer is a compile time error. The developer should decide if they want to compare the content or the address before comparing the objects.
• Given a, b := 0, 0, &a != &b. Even though the value of a and b is identical, when comparing pointer types, the address is what being compared.

This is great for equality comparison, which in many programming use-cases care about the compared type. However, when defining order is required, the type is less important, and different types can be ordered as long as the conversion is safe. For example, for a defined order over string types (func cmp(string, string) int { ... }), we should be able to sort a slice of *string (var s []*string). In this case, we would like to compare the value that is pointed by each element in the slice (call for any i, j: cmp(*s[i], *s[j])).

To generalize, when a three-way comparison function is defined over a type T, we can safely call it with another type U, and convert it to T, in the following cases:

• U is a pointer (or pointers chain) to a T.
• T is a pointer (or pointers chain) to a U.
• T and U are of the same kind.
• T and U are of the same number kind group (int?, uint?, float?, complex?) and U’s bits number is less or equal to T’s bits number.
• U and T are assignable structs.

The order package automatically checks for safe conversions according to the above rules, and apply them:

var ordInt64 = order.By(func(a, b int64) int { return int(a - b) })

func main() {
	var a, b int32
	if ordInt64.Is(a).GreaterEqual(b) { ... } // OK.

	int c, d unit64
	if ordInt64.Is(c).GreaterEqual(d) { ... } // Panics.
}

Multi Value Orderings

Structs in Go are a collection of fields, and each field can be of any Go type. Structs can be tested for equality using the == and != operators. However, they can’t be used with the order operators. It makes sense to define a three-way function func(T, T) int for that purpose. Let’s consider, for example, the following simple struct:

type person struct {
	name string
	age  int
}

In order to define order over persons we need to consider both the name and the age fields. If we want to order persons lexicographically by name, we also need to consider how will we order persons with the same name:

func threeWayPerson(a, b person) int {
	cmp := strings.Compare(a.name, b.name)
	if cmp == 0 {
		// Same name, order by age.
		return a.age - b.age
	}
	return cmp
}

What we did above is to define first and second ordering. It was to say: first order by name, then order by age. This is similar to the order by SQL statement or how we sort columns of a table in a spreadsheets program. We could generalize this technique: define a comparison function for each field, apply the functions by the importance order and return the first comparison that doesn’t tie:

cmps := []func (a, b person) int {
	func (a, b person) int { return strings.Compare(a.name, b.name) },
	func (a, b person) int { return a.age - b.age },
}

func threeWayPerson(a, b person) int {
	for _, cmp := range cmps {
	if v := cmp(a, b); v != 0 {
			return v
		}
	}
	return 0 // All comparisons tied.
}

This is what the order.By function does. The function accepts multiple three-way functions ordered by “importance”, and use this information in order to compare objects.

var ordPersons = order.By(
	func (a, b person) int { return strings.Compare(a.name, b.name) },
	func (a, b person) int { return a.age - b.age },
)

The ordPersons fully defines how to order any two persons, and can be used for any order task.

Ordering Tasks

Many tasks require order definition, and these tasks are automated by the order library. The most basic task is the condition: “is a b". The `order.Fns` object, returned by the `order.By` function, exposes the `Is` method that allows readable comparisons:

-if threeWayPerson(a, b) > 0 { … }
+if ordPersons.Is(a).Greater(b) { … }

Another ordering task is to sort a slice. Go’s standard library has the slice.Sort function, which gets a slice and a “less” function - a function that gets two indices in the slice and returns true if the element of the first index is less than the element of the second index. After having the order.Fns object, sorting slices is much easier:

-sort.Slice(persons, func(i, j) int { return threeWayPerson(persons[i], persons[j]) < 0 })
+ordPersons.Sort(persons)

Searching for an object in a sorted slice is another task. Go provides the slice.Search function which gets a slice and a “greater or equal” function and performs binary search. However, this function returns the first object that is greater or equal, so it might not be equal. Below we want to get the index of the object that equals to a person p into i, or the value -1 if the p does not appear in the slice. Again, it is much easier to use the order library to binary search a slice:

-i := sort.Search(persons, func(i) int { return threeWayPerson(persons[i], p) >= 0 })
-if (i >= len(persons) || threeWayPerson(persons[i], p) != p) {
-	i = -1
-}
+i := ordPersons.Search(persons, p)

And some other comparison tasks:

 // Is a slice sorted {persons[i] >= persons[j] | i > j}?
-sort.IsSorted(persons, func(i, j) int { return threeWayPerson(persons[i], persons[j]) < 0 })
+ordPersons.IsSorted(persons)
 // Is a slice strictly sorted {persons[i] > persons[j] | i > j}?
+ordPersons.IsStrictSorted(persons)
 // And functions which do not exist in the standard library:
 // Minimum and maximum values:
+minI, maxI := ordPersons.MinMax(persons)
+minPerson, maxPerson := persons[minI], persons[maxI]
 // Select k'th value:
+ordPersons.Select(persons, k)
+personK := persons[k]

Efficiency and Safety

The downside of the order library is that it exposes APIs that accept Go interface{}s, which is not type safe, and uses reflections in order to get the right value for comparison, which is not efficient. However, also Go’s sort.Slice, sort.IsSorted, sort.Search and friends use a similar methodology. On the upside, the code in the order library is thoroughly tested, thus reducing the chances for bugs after the type conversion, and additionally, makes the consuming code much shorter and readable, which reduces the chances for a bug there. It is recommended to wrap the calls for order functions with a typed version of the function, and add a short test that runs this function. This reduces the chances for bugs to zero.

type Person struct { ... }

var ordPersons = order.By(...)

func SearchPerson(persons []Person, p Person) int {
	return ordPersons.Sort(persons, p)
}

func TestSearchPersons(t *testing.T) {
	t.Parallel()
	i := SearchPersons([]Person{ {"foo", 42}, {"bar", 99} }, Person{"bar", 99})
	if got, want := i, 1; got != want {
		t.Errorf("Want %d, got: %d", want, got)
	}
}

Of course, once generics are introduced to Go, the order library could be rewritten in a type safe and efficient code.

Conclusions

We’ve discussed the difference between equality and ordering of objects, and understood the essential differences between the two. We’ve seen what sort of ordering tasks are there and how to tackle them in Go. Along the way, we’ve become familiar with the order library, and saw how it can help with ordering tasks.