Go generics: type constraint for map keys?

Question

In the code below, I define a generic linked list. Go1.18 is happy to use an instance of the list as a key to a map. However, the last line, when uncommented, doesn't compile; I get the error:

Cons[int] does not implement comparable

Is there a weaker type constraint I can use that picks out those types that can be used as keys, or is this intended, or is it a compiler bug?

package main

import "fmt"

type List[X any] interface {
    isList()
}

type Cons[X any] struct {
    Data X
    Next List[X]
}

func (Cons[X]) isList() {}

type Nil[X any] struct{}

func (Nil[X]) isList() {}

func id[X comparable](x X) X { return x }

func main() {
    x := Cons[int]{5, Nil[int]{}}
    m := map[List[int]]string{}
    m[x] = "Hi"        // succeeds
    fmt.Println(m[x])  // prints "Hi"
    // fmt.Println(id(x)) // fails
}

Paraldehyde

Answer 1

Go 1.20 (February 2023)

comparable is the correct catch-all constraint for map keys.

All types that are comparable as per the Go spec, even if the comparison may panic at run time, can satisfy the comparable constraint. Your code will compile as expected in 1.20.

This finally fixes the inconsistency in previous Go version about spec-comparable types vs comparable types. See below for details.

Go 1.18 and 1.19

The predeclared comparable constraint is the correct constraint for map keys, however it can be instantiated only by strictly comparable types, i.e. types that support == and != (condition for being used as map keys) but won't panic at run time. This excludes interfaces¹.

This is mentioned here: https://go.dev/ref/spec#Type_constraints

The predeclared interface type comparable denotes the set of all non-interface types that are comparable. Specifically, a type T implements comparable if:

• T is not an interface type and T supports the operations == and != ²
• T is an interface type and each type in T's type set implements comparable

Even though interfaces that are not type parameters can be compared (possibly causing a run-time panic) they do not implement comparable.

This is an important gotcha, because basic interface types normally do support the equality operators — what is compared is their dynamic types/values.

Therefore, your interface List[X] can be used as a map key directly, as in map[List[int]]string{}, but it does not implement comparable because it has an infinite type set (it has no terms, so any type implements it). And Cons doesn’t implement it either because it has a field of type List[X]. There is no "weaker" constraint for this.

Consider that constraints that embed comparable are also valid for map keys, so if you really need the method isList() in the function body, you can define a constraint like this, and have your lists-that-are-map-key structs implement that, instead of declaring an interface field:

// may use this as a constraint
type List interface {
    comparable
    isList() bool
}

---

^{1: the quote from the specs hints there are interface types that implement comparable, but it's effectively not possible to instantiate comparable with any interface at all: interfaces with only methods have an infinite type set, and interfaces with type terms can't be used anywhere except as constraints.}

^{2: this rule actually doesn't cover non-interface types that support ==, like type S struct { data any }, but these types still can't instantiate comparable https://go.dev/play/p/N-pmE0XC-hB. This is a bug in the spec.}

Cedric