Golang泛型之comparable

概念

comparable是golang新引入的预定义标识符，是一个接口，指代可以使用==或!=来进行比较的类型集合。

应用场景

comparable仅能用于泛型中的类型限定（type constraint）。

可直接作为类型限定使用，也可嵌入到类型限定中使用。

定义泛型Dictionary

golang spec对map的key有如下约束：

• key类型必须定义比较操作符==和!=；
• key类型必须不能是function、map或slice（没有定义比较操作符）；
• 对于interface类型，其动态类型必须定义比较操作符；
• 不满足上述约束，则会导致运行时异常（run-time panic）。

在golang中map被定义为一种由键（key）及索引值（value）构成的元素集合，实质上与python中Dictionary表达的是同一个东西。考虑到函数式编程中经常使用map来表示映射，在有些场景下我们可以通过将golang中的map重定义为Dictionary来减少概念上的混淆。

package main

import "fmt"

type Dictionay[K comparable, V any] map[K]V

func main() {
    dict := Dictionay[string, int]{"string": 1}
    fmt.Printf("dict: %#v \n", dict)
}

$ go run main.go 
dict: main.Dictionay[string,int]{"string":1} 

定义泛型Set

Golang并未提供内置的Set类型，不过一般我们可以利用map的key的唯一性来自定义Set类型。

package sets

// Set is a set of elements
type Set[T comparable] map[T]struct{}

// NewSet returns a set of elements with assigned type
func NewSet[T comparable](es ...T) Set[T] {
    s := Set[T]{}
    for _, e := range es {
        s.Add(e)
    }
    return s
}

// Len report the elements number of s
func (s *Set[T]) Len() int {
    return len(*s)
}

// IsEmpty report wether s is empty
func (s *Set[T]) IsEmpty() bool {
    return s.Len() == 0
}

// Add add elements to set s
// if element is already in s this has no effect
func (s *Set[T]) Add(es ...T) {
    for _, e := range es {
        (*s)[e] = struct{}{}
    }
}

// Remove remove elements from set s
// if element is not in s this has no effect
func (s *Set[T]) Remove(es ...T) {
    for _, e := range es {
        delete(*s, e)
    }
}

// Contains report wether v is in s
func (s *Set[T]) Contains(v T) bool {
    _, ok := (*s)[v] 
    return ok
}

// Clone create a new set with the same elements as s
func (s *Set[T]) Clone() Set[T] {
    r := Set[T]{}
    r.Add(s.ToSlice()...)
    return r
}

// ToSlice transform set to slice
func (s *Set[T]) ToSlice() []T {
    r := make([]T, 0, s.Len())

    for e := range *s {
        r = append(r, e)
    }

    return r
}

package sets

// Union the union of some sets(eg. A, B)
// is the set of elements that are in either A or B
func Union[T comparable](sets ...Set[T]) Set[T] {
    r := NewSet[T]()
    for _, s := range sets {
        r.Add(s.ToSlice()...)
    }
    return r
}

相应样例及运行结果如下：

package main

import (
    "fmt"

    "github.com/skholee/generic-wheel/sets"
)

func main() {
    s := sets.NewSet("a", "b", "c")
    s.Add("c", "d", "e")
    s.Remove("b", "d")
    fmt.Printf("set: %v \n", s.ToSlice())

    s = sets.Union(s, sets.NewSet("e", "f"), sets.NewSet("a", "f"))
    fmt.Printf("set: %v \n", s.ToSlice())

    s = sets.Intersect(s, sets.NewSet("a", "b", "c", "f", "g"))
    fmt.Printf("set: %v \n", s.ToSlice())

    s = sets.Difference(s, sets.NewSet("c", "f", "d"))
    fmt.Printf("set: %v \n", s.ToSlice())
}

$ go run .
set: [c e a] 
set: [a c e f] 
set: [c f a] 
set: [a] 

后记

通过自定义泛型Dictionary及Set，我们基本对golang泛型中的comparable类型限定有了一个大体的了解，同时也为后续进行golang泛型编程提供了一些基本可用的轮子。

完整代码见：https://github.com/skholee/generic-wheel

References

Golang泛型提案：https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md