Further constraining a type parameter in Golang (implementing generic List with Contains method)

Question

Let's say I want to write a generic List type with some useful methods, for example:

type List[T any] []T

func (l *List[T]) Len() int
func (l *List[T]) Get(pos int) (t T, err error)
func (l *List[T]) Set(pos int, t T) error
func (l *List[T]) Append(t ...T)
func (l *List[T]) Insert(t T, pos int) error
func (l *List[T]) Remove(pos int) (t T, err error)
// etc...

However, there are other useful methods that might require the list's element type T to be further constrained. For example, we can't implement a Contains method on this List type:

func (l *List[T]) Contains(t T) bool {
    for _, s := range *l {
        if s == t { // compiler error: invalid operation: s == t (incomparable types in type set)
            return true
        }
    }
    return false
}

We can only implement Contains if we declare List as

type List[T comparable] []T

But then this makes it impossible to make a List of a non-comparable type.

Is there a way to get the best of both worlds here? i.e. have a List[T] that can be used for non-comparable types T, but allow it to have a Contains method in the case that T is comparable?

I've thought of:

• using different types (e.g. UncomparableList/List or List/ComparableList)
• making Contains a function rather than a method

but I don't really like either of these.

Answer 1

Go doesn't have specialization so I don't think you can make it work exactly like this (not a generics expert, though).

I think a reasonably Go-ish way to go about this is to pass in an explicit comparator:

func (l *List[T]) Contains(t T, cmp func(T, T) bool) bool {
    for _, s := range *l {
        if cmp(s, t) {
            return true
        }
    }
    return false
}

Then you can do

func main() {
    list := List[int]([]int{1,2,3})
    fmt.Println(list.Contains(2, func(a, b int) bool { return a == b })) // true
}

For comparable types you could provide a default:

func Eq[T comparable](a, b T) bool {
    return a == b
}

So the above becomes

func main() {
    list := List[int]([]int{1,2,3})
    fmt.Println(list.Contains(2, Eq[int]) // true
}

You could also embed a comparator inside the List type and give it a default of func(a, b T) bool { return false } and expose a constructor that you can pass a custom comparator into. But that might be too implicit for your liking.

Answer 2

To answer the general question: IINM, Go doesn't allow the set of methods to depend on the type parameter.

If you wanted to add extra methods, you would have to embed the original type in an extended type. (In general, this is the only way you can sort-of do inheritance in Go).

type List[T any] []T

type ComparableList[T comparable] struct {
    List[T]
}

Then ComparableList inherits all the methods of List, so we can just define the Contains method on ComparableList:

func (l *ComparableList[T]) Contains(t T) bool {
    for _, s := range l.List {
        if s == t {
            return true
        }
    }
    return false
}

To be able to use the Contains method, we either make a ComparableList off the bat, or later convert a List to a ComparableList. We could write helper functions to do either of these:

func NewComparableList[T comparable]() ComparableList[T] {
    return ComparableList[T]{}
}

func MakeComparable[T comparable](l List[T]) ComparableList[T] {
    return ComparableList[T]{l}
}

Answer 3

Inspired by @isaactfa's answer, I thought of another way to do Contains for a non-comparable type.

Essentially, pass in a predicate func(T) bool to the Contains function, so Contains is checking if the list contains an element satisfying the predicate. For the usual case, the predicate will be func(t T) bool { return t == something }.

// Contains returns true if l contains an element satisfying the predicate f.
func (l *List[T]) Contains(f func(T) bool) bool {
    for _, t := range *l {
        if f(t) {
            return true
        }
    }
    return false
}

l := List[string]{}
l.Append("foo")
l.Contains(func(s string) bool { return s == "foo" }) // true

I'd probably even go one further and turn this into a Find function:

// Find finds the first element satisfying the given predicate f.
func (l *List[T]) Find(f func(T) bool) (pos int, t T, found bool) {
    for i, t := range *l {
        if f(t) {
            return i, t, true
        }
    }
    return
}

You could also define the default predicate for convenience:

func Is[T comparable](t T) func(T) bool {
    return func(s T) bool { return s == t }
}

l.Contains(Is("foo"))