Is there a Go generic type constraint that captures the ability to use a type as a key in a map?

Issue

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
}

Solution

The predeclared comparable constraint is the correct catch-all constraint for map keys, as it is implemented by types that support == and != (condition for being used as map keys), but not interfaces 1.

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

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.

Answered By – blackgreen

Answer Checked By – Timothy Miller (GoLangFix Admin)

Leave a Reply

Your email address will not be published.