Further constraining type parameters in Golang (using the Contains method to implement a generic List)

Question content

Suppose I want to write a general list type that contains some useful methods, such as:

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 may require further restricting the element types of the list t. For example, we cannot implement the 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

type List[T comparable] []T

But this makes it impossible to create a list of incomparable types.

Is there a way to get the best of both worlds? i.e. there is a list[t] available for an incomparable type t, but it is allowed to have a contains if t is comparable method?

I thought of:

• Use different types (e.g. uncomparablelist/list or list/comparablelist)
• Make contain as functions instead of methods

But I don’t really like any of them.

Correct answer

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

I think a reasonable go way to solve this problem is to pass 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

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

For similar types, you can provide a default value:

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 can also embed a comparator in the list type and assign it a default value func(a, b t) bool { return false } and expose a comparator that can be Define the constructor to which the comparator is passed. But this may be too obscure for you.

The above is the detailed content of Further constraining type parameters in Golang (using the Contains method to implement a generic List). For more information, please follow other related articles on the PHP Chinese website!