Go 博客
泛型接口
有一个想法,在你第一次听到它之前可能并不明显:由于接口本身就是类型,它们也可以拥有类型参数。事实证明,在表达泛型函数和类型的约束时,这个想法出奇地强大。在这篇文章中,我们将通过讨论在一些常见场景中使用带有类型参数的接口来演示这一点。
一个简单的树集合
作为激励性示例,假设我们需要一个二叉搜索树的泛型版本。存储在此类树中的元素需要是有序的,因此我们的类型参数需要一个约束来确定要使用的排序。一个简单的选择是使用 Go 1.21 中引入的 cmp.Ordered 约束。它将类型参数限制为有序类型(字符串和数字),并允许类型的方法使用内置的排序运算符。
// The zero value of a Tree is a ready-to-use empty tree.
type Tree[E cmp.Ordered] struct {
root *node[E]
}
func (t *Tree[E]) Insert(element E) {
t.root = t.root.insert(element)
}
type node[E cmp.Ordered] struct {
value E
left *node[E]
right *node[E]
}
func (n *node[E]) insert(element E) *node[E] {
if n == nil {
return &node[E]{value: element}
}
switch {
case element < n.value:
n.left = n.left.insert(element)
case element > n.value:
n.right = n.right.insert(element)
}
return n
}
(演练)
然而,这种方法有一个缺点,即它只适用于定义了 <
的基本类型;你不能插入像 time.Time 这样的结构体类型。
我们可以通过要求用户提供一个比较函数来弥补这一点
// A FuncTree must be created with NewTreeFunc.
type FuncTree[E any] struct {
root *funcNode[E]
cmp func(E, E) int
}
func NewFuncTree[E any](cmp func(E, E) int) *FuncTree[E] {
return &FuncTree[E]{cmp: cmp}
}
func (t *FuncTree[E]) Insert(element E) {
t.root = t.root.insert(t.cmp, element)
}
type funcNode[E any] struct {
value E
left *funcNode[E]
right *funcNode[E]
}
func (n *funcNode[E]) insert(cmp func(E, E) int, element E) *funcNode[E] {
if n == nil {
return &funcNode[E]{value: element}
}
sign := cmp(element, n.value)
switch {
case sign < 0:
n.left = n.left.insert(cmp, element)
case sign > 0:
n.right = n.right.insert(cmp, element)
}
return n
}
(演练)
这可行,但也伴随着缺点。我们不能再使用容器类型的零值,因为它需要有一个显式初始化的比较函数。而且函数字段的使用使得编译器更难内联比较调用,这可能会引入显著的运行时开销。
在元素类型上使用方法可以解决这些问题,因为方法直接与类型关联。方法不必显式传递,编译器可以看到调用的目标,并且可能能够内联它。但是我们如何表达约束以要求元素类型提供必要的方法呢?
在约束中使用接收者
我们可能尝试的第一种方法是定义一个带有 Compare
方法的普通旧接口
type Comparer interface {
Compare(Comparer) int
}
然而,我们很快意识到这效果不佳。要实现此接口,方法的参数本身必须是 Comparer
。这不仅意味着此方法的实现必须将其参数类型断言为其自己的类型,而且还要求每个类型都必须显式地按名称引用我们的带有 Comparer
类型的包(否则方法签名将不相同)。这不是很正交。
更好的方法是使 Comparer
接口本身泛型化
type Comparer[T any] interface {
Compare(T) int
}
这个 Comparer
现在描述了一整个接口家族,每个 Comparer
可能实例化的类型都有一个。一个实现了 Comparer[T]
的类型声明“我可以与一个 T
进行比较”。例如,time.Time
自然地实现了 Comparer[time.Time]
,因为它有一个匹配的 Compare
方法
// Implements Comparer[Time]
func (t Time) Compare(u Time) int
这更好,但还不够。我们真正想要的是一个约束,它表示类型参数可以与自身进行比较:我们希望约束是自引用的。微妙的洞察是,自引用方面不必是接口定义本身的一部分;具体来说,Comparer
类型中 T
的约束只是 any
。相反,它是我们如何将 Comparer
用作 MethodTree
的类型参数的约束的结果
// The zero value of a MethodTree is a ready-to-use empty tree.
type MethodTree[E Comparer[E]] struct {
root *methodNode[E]
}
func (t *MethodTree[E]) Insert(element E) {
t.root = t.root.insert(element)
}
type methodNode[E Comparer[E]] struct {
value E
left *methodNode[E]
right *methodNode[E]
}
func (n *methodNode[E]) insert(element E) *methodNode[E] {
if n == nil {
return &methodNode[E]{value: element}
}
sign := element.Compare(n.value)
switch {
case sign < 0:
n.left = n.left.insert(element)
case sign > 0:
n.right = n.right.insert(element)
}
return n
}
(演练)
因为 time.Time
实现了 Comparer[time.Time]
,所以它现在是这个容器的有效类型实参,我们仍然可以使用零值作为空容器
var t MethodTree[time.Time]
t.Insert(time.Now())
为了获得完全的灵活性,库可以提供所有三个 API 版本。如果我们要最大限度地减少重复,所有版本都可以使用共享实现。我们可以为此使用函数版本,因为它最通用
type node[E any] struct {
value E
left *node[E]
right *node[E]
}
func (n *node[E]) insert(cmp func(E, E) int, element E) *node[E] {
if n == nil {
return &node[E]{value: element}
}
sign := cmp(element, n.value)
switch {
case sign < 0:
n.left = n.left.insert(cmp, element)
case sign > 0:
n.right = n.right.insert(cmp, element)
}
return n
}
// Insert inserts element into the tree, if E implements cmp.Ordered.
func (t *Tree[E]) Insert(element E) {
t.root = t.root.insert(cmp.Compare[E], element)
}
// Insert inserts element into the tree, using the provided comparison function.
func (t *FuncTree[E]) Insert(element E) {
t.root = t.root.insert(t.cmp, element)
}
// Insert inserts element into the tree, if E implements Comparer[E].
func (t *MethodTree[E]) Insert(element E) {
t.root = t.root.insert(E.Compare, element)
}
(演练)
这里的一个重要观察是,共享实现(基于函数的变体)没有任何限制。它必须保持最大限度的灵活性以作为公共核心。我们也不会将比较函数存储在结构字段中。相反,我们将其作为参数传递,因为函数参数比结构字段更容易让编译器分析。
当然,仍然存在一定量的样板代码。所有导出的实现都需要使用略有不同的调用模式来复制完整的 API。但这一部分编写和阅读起来都很简单。
组合方法和类型集
我们可以使用我们的新树数据结构来实现一个有序集合,以对数时间提供元素查找。现在让我们想象一下我们需要使查找以常数时间运行;我们可能会尝试通过在树旁边维护一个普通的 Go map 来实现这一点
type OrderedSet[E Comparer[E]] struct {
tree MethodTree[E] // for efficient iteration in order
elements map[E]bool // for (near) constant time lookup
}
func (s *OrderedSet[E]) Has(e E) bool {
return s.elements[e]
}
func (s *OrderedSet[E]) Insert(e E) {
if s.elements == nil {
s.elements = make(map[E]bool)
}
if s.elements[e] {
return
}
s.elements[e] = true
s.tree.Insert(e)
}
func (s *OrderedSet[E]) All() iter.Seq[E] {
return func(yield func(E) bool) {
s.tree.root.all(yield)
}
}
func (n *node[E]) all(yield func(E) bool) bool {
return n == nil || (n.left.all(yield) && yield(n.value) && n.right.all(yield))
}
(演练)
然而,编译此代码将产生错误
无效的 map 键类型 E(缺少 comparable 约束)
错误消息告诉我们,我们需要进一步约束我们的类型参数才能将其用作 map 键。`comparable` 约束是一个特殊的预声明约束,所有定义了相等运算符 `==` 和 `!=` 的类型都满足它。在 Go 中,这也是可以作为内置 `map` 类型的键的类型集。
我们有三种选择来将此约束添加到我们的类型参数中,所有这些都有不同的权衡
-
我们可以将 `comparable` 嵌入到我们原始的 `Comparer` 定义中(演练)
type Comparer[E any] interface { comparable Compare(E) int }
这有一个缺点,它还会使我们的 `Tree` 类型只能用于 `comparable` 的类型。通常,我们不希望不必要地限制泛型类型。
-
我们可以添加一个新的约束定义(演练)。
type Comparer[E any] interface { Compare(E) int } type ComparableComparer[E any] interface { comparable Comparer[E] }
这很整洁,但它在我们的 API 中引入了一个新的标识符(`ComparableComparer`),而命名是困难的。
-
我们可以将约束内联到我们的受更多约束的类型中(演练)
type OrderedSet[E interface { comparable Comparer[E] }] struct { tree Tree[E] elements map[E]struct{} }
这可能会变得有点难以阅读,特别是如果它需要经常发生。它也使得在其他地方重用约束变得更加困难。
使用哪种方法是一种风格选择,最终取决于个人偏好。
(不)约束泛型接口
此时值得讨论泛型接口的约束。您可能想为一个泛型容器类型定义一个接口。例如,假设您有一个算法需要一个集合数据结构。有许多不同种类的集合实现,具有不同的权衡。为所需的集合操作定义一个接口可以增加您的包的灵活性,将适用于特定应用程序的权衡决策留给用户
type Set[E any] interface {
Insert(E)
Delete(E)
Has(E) bool
All() iter.Seq[E]
}
这里一个自然的问题是,这个接口应该有什么约束。如果可能的话,泛型接口上的类型参数应该使用 `any` 作为约束,允许任意类型。
从我们上面的讨论来看,原因应该很清楚:不同的具体实现可能需要不同的约束。我们上面检查过的所有 `Tree` 类型,以及 `OrderedSet` 类型,都可以为其元素类型实现 `Set`,尽管这些类型有不同的约束。
定义接口的目的是将实现留给用户。由于无法预测用户可能希望对其实现施加什么样的约束,因此请尽量将任何约束(强于 `any` 的)留给具体实现,而不是接口。
指针接收者
让我们尝试在一个例子中使用 `Set` 接口。考虑一个从序列中删除重复元素的函数
// Unique removes duplicate elements from the input sequence, yielding only
// the first instance of any element.
func Unique[E comparable](input iter.Seq[E]) iter.Seq[E] {
return func(yield func(E) bool) {
seen := make(map[E]bool)
for v := range input {
if seen[v] {
continue
}
if !yield(v) {
return
}
seen[v] = true
}
}
}
(演练)
这使用 `map[E]bool` 作为 `E` 元素的简单集合。因此,它只适用于 `comparable` 类型,这些类型定义了内置的相等运算符。如果我们要将其推广到任意类型,我们需要用一个泛型集合替换它
// Unique removes duplicate elements from the input sequence, yielding only
// the first instance of any element.
func Unique[E any](input iter.Seq[E]) iter.Seq[E] {
return func(yield func(E) bool) {
var seen Set[E]
for v := range input {
if seen.Has(v) {
continue
}
if !yield(v) {
return
}
seen.Insert(v)
}
}
}
(演练)
然而,这不起作用。`Set[E]` 是一个接口类型,`seen` 变量将被初始化为 `nil`。我们需要使用 `Set[E]` 接口的具体实现。但是正如我们在本文中看到的那样,没有通用的集合实现适用于 `any` 元素类型。
我们必须要求用户提供一个我们可以使用的具体实现,作为额外的类型参数
// Unique removes duplicate elements from the input sequence, yielding only
// the first instance of any element.
func Unique[E any, S Set[E]](input iter.Seq[E]) iter.Seq[E] {
return func(yield func(E) bool) {
var seen S
for v := range input {
if seen.Has(v) {
continue
}
if !yield(v) {
return
}
seen.Insert(v)
}
}
}
(演练)
然而,如果我们将它与我们的集合实现一起实例化,我们就会遇到另一个问题
// OrderedSet[E] does not satisfy Set[E] (method All has pointer receiver)
Unique[E, OrderedSet[E]](slices.Values(s))
// panic: invalid memory address or nil pointer dereference
Unique[E, *OrderedSet[E]](slices.Values(s))
第一个问题从错误消息中就很清楚:我们的类型约束表明 `S` 的类型实参需要实现 `Set[E]` 接口。由于 `OrderedSet` 上的方法使用指针接收者,因此类型实参也必须是指针类型。
当尝试这样做时,我们遇到了第二个问题。这源于我们在实现中声明了一个变量的事实
var seen S
如果 `S` 是 `*OrderedSet[E]`,则变量将像以前一样用 `nil` 初始化。调用 `seen.Insert` 会导致 panic。
如果我们只有指针类型,我们就无法获得值类型的有效变量。如果我们只有值类型,我们就无法调用它的指针方法。结果是我们需要值和指针类型。因此我们必须引入一个额外的类型参数 `PS` 和一个新的约束 `PtrToSet`
// PtrToSet is implemented by a pointer type implementing the Set[E] interface.
type PtrToSet[S, E any] interface {
*S
Set[E]
}
// Unique removes duplicate elements from the input sequence, yielding only
// the first instance of any element.
func Unique[E, S any, PS PtrToSet[S, E]](input iter.Seq[E]) iter.Seq[E] {
return func(yield func(E) bool) {
// We convert to PS, as only that is constrained to have the methods.
// The conversion is allowed, because the type set of PS only contains *S.
seen := PS(new(S))
for v := range input {
if seen.Has(v) {
continue
}
if !yield(v) {
return
}
seen.Insert(v)
}
}
}
(演练)
这里的诀窍是通过 `PtrToSet` 接口上的额外类型参数在函数签名中连接两个类型参数。`S` 本身没有约束,但 `PS` 必须是类型 `*S`,并且它必须具有我们需要的方法。所以实际上,我们限制 `S` 具有一些方法,但这些方法需要使用指针接收者。
虽然用这种约束定义函数需要一个额外的类型参数,但重要的是这并不会使使用它的代码复杂化:只要这个额外的类型参数位于类型参数列表的末尾,它就可以被推断出来
// The third type argument is inferred to be *OrderedSet[int]
Unique[int, OrderedSet[int]](slices.Values(s))
这是一个通用模式,值得记住:当你在别人的作品中遇到它,或者当你想在自己的作品中使用它时。
func SomeFunction[T any, PT interface{ *T; SomeMethods }]()
如果您有两个类型参数,其中一个被约束为指向另一个的指针,则该约束确保相关方法使用指针接收者。
您应该约束为指针接收者吗?
此时,您可能会感到非常不知所措。这相当复杂,期望每个 Go 程序员都能理解这个函数签名中发生了什么似乎是不合理的。我们还不得不在我们的 API 中引入更多的名称。当人们最初警告不要向 Go 添加泛型时,这就是他们担心的事情之一。
所以,如果您发现自己陷入了这些问题,值得退一步思考。我们通常可以通过以不同的方式思考我们的问题来避免这种复杂性。在这个例子中,我们构建了一个函数,它接受一个 `iter.Seq[E]` 并返回一个带有唯一元素的 `iter.Seq[E]`。但要进行去重,我们需要将唯一元素收集到一个集合中。由于这要求我们为整个结果分配空间,所以将结果表示为流并不能真正受益。
如果我们重新思考这个问题,我们可以通过使用 `Set[E]` 作为常规接口值来完全避免额外的类型参数
// InsertAll adds all unique elements from seq into set.
func InsertAll[E any](set Set[E], seq iter.Seq[E]) {
for v := range seq {
set.Insert(v)
}
}
(演练)
通过将 `Set` 用作普通的接口类型,很明显调用者必须提供其具体实现的有效值。这是一种非常常见的模式。如果他们需要 `iter.Seq[E]`,他们只需调用 `set` 上的 `All()` 即可获取一个。
这会稍微使调用者的事情复杂化,但它比对指针接收器的约束有另一个优势:请记住,我们最初使用 `map[E]bool` 作为简单的集合类型。在此基础上很容易实现 `Set[E]` 接口
type HashSet[E comparable] map[E]bool
func (s HashSet[E]) Insert(v E) { s[v] = true }
func (s HashSet[E]) Delete(v E) { delete(s, v) }
func (s HashSet[E]) Has(v E) bool { return s[v] }
func (s HashSet[E]) All() iter.Seq[E] { return maps.Keys(s) }
(演练)
此实现不使用指针接收器。因此,尽管这完全有效,但它无法与复杂的指针接收器约束一起使用。但它适用于我们的 `InsertAll` 版本。与许多约束一样,强制方法使用指针接收器对于许多实际用例来说可能过于严格。
结论
我希望这能说明接口上的类型参数所带来的一些模式和权衡。它是一个强大的工具,但也伴随着成本。主要收获是
- 使用泛型接口通过自引用方式表达对接收者的约束。
- 使用它们在不同的类型参数之间创建受约束的关系。
- 使用它们抽象不同实现和不同类型约束。
- 当您发现自己需要约束为指针接收器时,请考虑是否可以重构代码以避免额外的复杂性。请参阅“您应该约束为指针接收器吗?”。
一如既往,不要过度设计:一个灵活性较低但更简单、更易读的解决方案最终可能是更明智的选择。
下一篇文章:FIPS 140-3 Go 密码模块
上一篇文章:[ 有 | 无 ] 错误处理的语法支持
博客索引