go struct with generics implementing comparable

Issue

Consider the following code snippet for version go1.18beta2 linux/amd64

    type Vector[T comparable] struct {
       data_ []T
    }
    
    func (v *Vector[T]) Contains(e T) bool {
       for _, x := range v.data_ {
          if x == e {
             return true
          }
       }
       return false
    }
    
    func TestVector(t *testing.T) {
       v2 := Vector[Vector[int]]{}
    }

This does not compile and gives error: “Vector[int] does not implement comparable” simply because Vector has no equality operators defined. However, I cannot find how to define them.

Question: Is this approach of creating a comparable struct not allowed, and why; or is the documentation not written yet?

Solution

The constraint comparable is predeclared and supported by the language specifications. You can’t "manually" make a type implement it. The documentation is available in the tip version of the specs (under Type Constraints):

The predeclared interface type comparable denotes the set of all concrete (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 !=; or
  • T is an interface type and each type in T‘s type set implements comparable.

Your type Vector[T comparable] doesn’t meet any of those conditions. It is not an interface type, and it does not otherwise support the equality operations. This follows from the specs about comparison operators linked in the quote above, regardless of type parameters:

Struct values are comparable if all their fields are comparable. Two struct values are equal if their corresponding non-blank fields are equal.

[…]

Slice, map, and function values are not comparable

And the field data_ []T, even if T is constrained by comparable is not comparable because it’s a slice type, and slice types are not comparable.

The purpose of the comparable constraint is really just to allow writing generic code with == and != operators. If a type is not comparable by design, you can’t write such code. That would be true even if Vector didn’t have a type parameter.

If your goal is to allow equality tests between instances of Vector[T], you might want to add an Equal method that takes care of this specific use case (only vectors instantiated with the same type parameter will be allowed):

func (v *Vector[T]) Equal(e Vector[T]) bool {
    // test equality in a way that makes sense for this type
}

Worth mentioning that there is a way to make Vector[T comparable] comparable itself, i.e. change the data_ field to be a pointer-to-slice:

type Vector[T comparable] struct {
    data_ *[]T
}

Now instantiation with Vector[Vector[int]] compiles. However, beside being very cumbersome to initialize with struct literals (playground), it comes with all caveats of pointer comparison. More specifically:

Two pointer values are equal if they point to the same variable or if both have value nil. Pointers to distinct zero-size variables may or may not be equal.

Now the comparison x == e tests that the memory address stored in the data_ field in x and e is the same. This might skew the semantics of comparing two Vector[T] instances — is it correct to say that two vector instances are equal if they hold a reference to the same slice? Maybe. It depends on the assumptions your program wants to make. Personally, I don’t think this is actually better than having a separate Equal method and/or redesigning your data types, but as usual, YMMV.

Answered By – blackgreen

Answer Checked By – Katrina (GoLangFix Volunteer)

Leave a Reply

Your email address will not be published.