The Weird Type System of Golang

I am excited about Golang and its simplicity. I have been learning Go on and off for the past... 7 years? But only recently I decided to do it somewhat seriously. And while Go is fun, and simple, the more I dig deeper, the more inconsistent it feels. In this article, we will see some of these inconsistencies in practice, as we try to create a generic binary search.

Generic programming is one of the most fascinating tools in computer science. It is both one of these cool-sounding academic ideas, while at the same time being quite practical. In this article, I will try a little bit of practical generic programming, and I claim, quite simple too! A generic binary search.

It makes sense right? A lot of things can be compared with one another, and if you can compare them, you can sort them and search them with binary search. The binary search algorithm is the same for anything that can be compared, so it makes sense to want to code it as a single generic function that works for many types. What changes for each different type is not the core algorithm, but only how you compare two instances of this type. And for this exact reason, Go's standard library conveniently provides sort.Search().

You just provide it a way to compare two things, and then you can perform binary search on a slice of these things (actually, it is not even tied to slices but this is out of scope). For example, you would write a binary search on a slice of int like this (item is the int you search for):

var items []int
// ...
sort.Search(len(items), func(i int) bool { 
  return item < items[i] 
})

Now, suppose you make your custom type KeyValue, which is an arbitrary key-value pair, e.g.,:

type KeyValue struct {
  key   int;
  value int;
}

Say that KeyValue A is less than KeyValue B if A.key < B.key. Great, you can still use sort.Search(). You just write (again, item is the KeyValue you search for):

var items []KeyValue
// ...
sort.Search(len(items), func(i int) bool { 
  return item.key < items[i].key
})

Wouldn't it be great if we could wrap this call to sort.Search() in a function that takes a slice of any type? The main obstacle as we saw is not in sort.Search(). We can reuse that as is for all the types. The problem is in the comparison. Different types have different comparisons (as e.g., with KeyValue). Based on my Go knowledge, the natural solution to this problem is an interface.

We can create an interface with a less() function like this:

type Item interface {
  less(than Item) bool
}

Now, we can write our beloved generic function once:

func bin_search(item Item, items []Item) {
  sort.Search(len(items), func (i int) bool  {
    return item.less(items[i])
  })
}

And the only thing we have to do so that we can use this function on KeyValue's is to just implement less() for this type. It is reasonable that we have to do that because again, comparisons differ for each type.

func (kv KeyValue) less(item Item) bool {
  return kv.key < item.(KeyValue).key
}

Fantastic right? Here is the full compilable code so far:

package main

import "sort"

type Item interface {
  less(than Item) bool
}

type KeyValue struct {
  key   int
  value int
}

func (kv KeyValue) less(than Item) bool {
  return kv.key < than.(KeyValue).key
}

func bin_search(item Item, items []Item) {
  sort.Search(len(items), func(i int) bool {
    return item.less(items[i])
  })
}

func main() {
}

Unfortunately, we are not done so easily... Let's try to write some code in main() that uses bin_search().

func  main() {
  var items []KeyValue
  var item  KeyValue
  bin_search(item, items)
}

This will give an error. The compiler will complain about the second argument of the call to bin_search(), i.e., items. It says that we cannot pass a []KeyValue to a []Item, even though KeyValue implements Item. You may think there is an overarching reason for the way the type-checking of function arguments works in Go that validates this error. For example, we might think that the argument and parameters types must be exactly the same in Go. Well, no. Because you see, the compiler does not complain about the first argument. So, it's ok to pass a KeyValue to an Item, because KeyValue implements Item, but when you lift this reasoning to slices, it fails . Honestly, this makes 0 sense to me...

If we try to work with int's, then there's no hope to begin with... int is a primitive type, and you can't implement an interface for a primitive type. Again, I do not know why. But all that means that our "generic" function, is not all that generic after all. Actually, it's worse in my humble opinion. It pretends to be generic, but in practice it is not.

All right, let's not give up so quickly... First, the []KeyValue must become a []Item so that we can pass it. You might be thinking "can't we cast/convert it at the call site?". Something like you you convert a string to []byte by doing []byte("your string"). But no, here we can't do []Item(items) (or at least, I don't know how to make this compile). So, we have to do something like this:

func  main() {
  // Make items []Item instead of []KeyValue
  var items []Item
  var item  KeyValue
  bin_search(item, items)
}

We might say it is not a big of a change, but it actually is. You obviously won't be passing empty slices around. You have to fill the slice. So, you can append() a KeyValue to a []KeyValue, and you can append() an Item to a []Item, but also, you can append a KeyValue to a []Item.

But here's the funny part. You see, just as you can append a KeyValue to a []Item because KeyValue implements Item, you can append any other instance of a type that implements Item. In other words, we can create an arbitrary type Foo that implements Item, and append() a Foo to items:

type Foo struct {
  a float32
  b float32
}

func (foo Foo) less(than Item) bool {
  return foo.b < than.(Foo).b
}

func main() {
  var items []Item
  var foo Foo
  var kv KeyValue

  items = append(items, kv)
  items = append(items, foo)

  var item KeyValue
  bin_search(item, items)
}

Remember that we want items to be a []KeyValue. The only reason we made it a []Item was so that we can pass it to bin_search(). But this comes at the price of type safety (this lack of type safe exists in all the implementations of less() too). Now, we can append whatever (Item) to items. I'll come back to a solution to this problem, but first let's see what are we going to do with the other, earlier problem with int. We have no way to work with them.

So, here's how people work around this problem. They do type Int int. And then, they write code like this:

type Int int

func (i Int) less(than Item) bool {
  return i < than.(Int)
}

func main() {
  var items []Item

  items = append(items, Int(2))
  items = append(items, Int(3))

  bin_search(item, items)
}

No, I am not kidding... Because Int is a custom type, we can implement Item for it. But this also means that we still cannot append() say, 5. We have to wrap it in an Int. People have to actually write such stuff.

Apart from the fact that it's weird that you have to do all that, this highlights another problem. I thought that type T Q makes T the same type as Q, i.e., full type equality. But as it is apparent from the example above, this is not the case. An Int is not an int. A possible explanation would be to say that type T Q means "you can create a T from a Q". That would explain that you can do Int(5). But that doesn't make sense either, because suppose you do type T []int. If a function gets a T, and you try to pass an []int, the compiler will not complain. You do not have to write T(<your []int>) at the call site. You just pass your []int straight.

Anyway, let's get back to business. We have this type safety problem mentioned earlier. I thought I'd throw generics to the problem, a recent feature of Go. Let's write bin_search() as below:

func bin_search[T Item](item T, items []T) {
  sort.Search(len(items), func(i int) bool {
    return item.less(items[i])
  })
}

func main() {
  var items []KeyValue
  var kv KeyValue

  items = append(items, kv)

  bin_search(kv, items)
}

This actually works! We say that T implements Item, and bin_search() gets a []T. So, we can pass []KeyValue to bin_search().

But... we still have the problem. This still does not work for int, for the same reason as before. The weird thing is that Go has a built-in interface called comparable. Anything that implements this interface means that it supports operators == and !=. Neither is enough to use in the binary search but here's the weird part. Suppose they were enough. Then, we would make T be comparable and bin_search() would work for int. However, you cannot implement comparable for a custom type, which means that then our function would not work for KeyValue. It's as if we inverted the original problem. We cannot implement custom interfaces for built-in types, and we also cannot implement built-in interfaces for custom types 🤷.

I don't know... Go seems weirder the deeper I dig. Maybe I miss something, as practically I am new to Go. But I feel that this was a big exploration already, and if Go is that simple, then I should have found a solution.

I also want to emphasize that this problem I tried to solve was a simple one. One that Go should be able to solve. I didn't want to do C++'s CRTP, I didn't try to use any fancy introspection and type traits (and I feel that those things would conflict with Go's striving for simplicity). All I wanted to do is basically create a generic "less than" operator that can work with the rest of the type system. Go has interfaces and recently it got generics; we should be able to solve this simple problem.

As a last note, I feel Go has a rough take in simplicity. I wish this wasn't my impression, but, it feels as Go is simplistic and not simple. Being simple is actually very hard, because you need to provide a simple set of language features that you can compose arbitrarily to achieve all sorts of things; what Go calls orthogonality. But Go seems to miss basic composition. The fact that you can pass a KeyValue to an Item but not a []KeyValue to an []Item still blows my mind... Like what, two central concepts in the language, slices and interfaces, can't compose in this simple scenario?

Anyway, I would be interested to hear the thoughts of more experienced Gophers.