本文来自正在规划的Go语言&云原生自我提升系列,欢迎关注后续文章。
泛型函数抽象算法
我们也可以编写函数。前面提到没有泛型会很难编写适用所有类型的映射、归约(reduce)和过滤实现。泛型使其变得简单。以下是类型参数提案中的一些实现:
// Map turns a []T1 to a []T2 using a mapping function.
// This function has two type parameters, T1 and T2.
// This works with slices of any type.
func Map[T1, T2 any](s []T1, f func(T1) T2) []T2 {
r := make([]T2, len(s))
for i, v := range s {
r[i] = f(v)
}
return r
}
// Reduce reduces a []T1 to a single value using a reduction function.
func Reduce[T1, T2 any](s []T1, initializer T2, f func(T2, T1) T2) T2 {
r := initializer
for _, v := range s {
r = f(r, v)
}
return r
}
// Filter filters values from a slice using a filter function.
// It returns a new slice with only the elements of s
// for which f returned true.
func Filter[T any](s []T, f func(T) bool) []T {
var r []T
for _, v := range s {
if f(v) {
r = append(r, v)
}
}
return r
}
函数将类型参数放在函数名和变量参数之间。Map
和Reduce
有两个类型参数,都是any
类型,而Filter
为一个参数。运行如下代码时:
words := []string{"One", "Potato", "Two", "Potato"}
filtered := Filter(words, func(s string) bool {
return s != "Potato"
})
fmt.Println(filtered)
lengths := Map(filtered, func(s string) int {
return len(s)
})
fmt.Println(lengths)
sum := Reduce(lengths, 0, func(acc int, val int) int {
return acc + val
})
fmt.Println(sum)
会得到如下输出:
[One Two]
[3 3]
6
读者可自行使用Go Playground或第8章的GitHub代码库sample_code/map_filter_reduce目录中的代码进行测试。
泛型和接口
可以使用任意接口来进行类型约束,不只是有any
和comparable
。例如希望创建一个存储任意实现了fmt.Stringer
的同类型两个值的类型。泛型使得我们可以在编译时进行这一强制:
type Pair[T fmt.Stringer] struct {
Val1 T
Val2 T
}
也可以创建带类型参数的接口。例如,下面有一个包含指定类型值比较方法并返回float64
的接口。还内嵌了fmt.Stringer
:
type Differ[T any] interface {
fmt.Stringer
Diff(T) float64
}
我们会使用这两个类型创建对比函数。该函数接口两个包含Differ
类型字段的Pair
实例,返回带更接近值的Pair
:
func FindCloser[T Differ[T]](pair1, pair2 Pair[T]) Pair[T] {
d1 := pair1.Val1.Diff(pair1.Val2)
d2 := pair2.Val1.Diff(pair2.Val2)
if d1 < d2 {
return pair1
}
return pair2
}
FindCloser
接收包含实现了Differ
接口的字段的Pair
实例。Pair
要求两个字段的类型相同,并且该类型实现fmt.Stringer
接口,该函数要求更高。如果Pair
实例中的字段未实现Differ
,编译器会不允许使用带FindCloser
的Pair
实例。
下面定义几个实现Differ
接口的类型:
type Point2D struct {
X, Y int
}
func (p2 Point2D) String() string {
return fmt.Sprintf("{%d,%d}", p2.X, p2.Y)
}
func (p2 Point2D) Diff(from Point2D) float64 {
x := p2.X - from.X
y := p2.Y - from.Y
return math.Sqrt(float64(x*x) + float64(y*y))
}
type Point3D struct {
X, Y, Z int
}
func (p3 Point3D) String() string {
return fmt.Sprintf("{%d,%d,%d}", p3.X, p3.Y, p3.Z)
}
func (p3 Point3D) Diff(from Point3D) float64 {
x := p3.X - from.X
y := p3.Y - from.Y
z := p3.Z - from.Z
return math.Sqrt(float64(x*x) + float64(y*y) + float64(z*z))
}
该代码的使用如下:
func main() {
pair2Da := Pair[Point2D]{Point2D{1, 1}, Point2D{5, 5}}
pair2Db := Pair[Point2D]{Point2D{10, 10}, Point2D{15, 5}}
closer := FindCloser(pair2Da, pair2Db)
fmt.Println(closer)
pair3Da := Pair[Point3D]{Point3D{1, 1, 10}, Point3D{5, 5, 0}}
pair3Db := Pair[Point3D]{Point3D{10, 10, 10}, Point3D{11, 5, 0}}
closer2 := FindCloser(pair3Da, pair3Db)
fmt.Println(closer2)
}
可在The Go Playground中运行或查看第8章的GitHub代码库sample_code/generic_interface目录中的代码。
使用类型名指定运算符
泛型还需要体现另外一点:运算符。divAndRemainder
函数可正常操作int
,而应用于其它类型则需要进行类型转换,并且uint
可存储的值远大于int
。如果要为divAndRemainder
编写一个泛型版本,需要一种方式来指定可使用/
和%
。Go泛型通过类型元素来实现,由接口内的一种或多种类型名指定:
type Integer interface {
int | int8 | int16 | int32 | int64 |
uint | uint8 | uint16 | uint32 | uint64 | uintptr
}
在使用内嵌实现组合一节中,我们学习过嵌套接口表明所包含的接口的方法接包括内嵌接口的方法。类型元素指定类型参数可赋哪些类型,以及支持哪些运算符。通过|
来分隔具体类型。允许的运算符为对所有列出类型有效的那些。模运算符(%
) 仅对整型有效,所有我们列举了所有的整型。(可以不加byte
和rune
,因为它们分别是uint8
和int32
的类型别名。)
注意带类型元素的接口仅对类型约束有效。将它们用作变量、字段、返回值或参数类似会报编译时错误。
现在可以编写divAndRemainder
的泛型版本,通过uint
内置类型使用该函数(或其它Integer
中所列的类型):
func divAndRemainder[T Integer](num, denom T) (T, T, error) {
if denom == 0 {
return 0, 0, errors.New("cannot divide by zero")
}
return num / denom, num % denom, nil
}
func main() {
var a uint = 18_446_744_073_709_551_615
var b uint = 9_223_372_036_854_775_808
fmt.Println(divAndRemainder(a, b))
}
默认,类型名完全匹配。如对divAndRemainder
使用底层为Integer
所列类型的自定义类型,会出现错误。以下代码:
type MyInt int
var myA MyInt = 10
var myB MyInt = 20
fmt.Println(divAndRemainder(myA, myB))
会报如下错误:
MyInt does not satisfy Integer (possibly missing ~ for int in Integer)
错误文本提示了如何解决这一问题。如果希望类型名对那些以这些类型为底层类型的类型也有效,在类型名前加~
。那么我们的Integer
定义就变成了:
type Integer interface {
~int | ~int8 | ~int16 | ~int32 | ~int64 |
~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}
可在The Go Playground 或第8章的GitHub代码库的sample_code/type_terms目录下查看divAndRemainder
的泛型版本。
类型名让我们可以定义用于编写泛型比较函数的类型:
type Ordered interface {
~int | ~int8 | ~int16 | ~int32 | ~int64 |
~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
~float32 | ~float64 |
~string
}
Ordered
接口列举了所有支持==
, !=
, <
, >
, <=
和>=
运算符的类型。因为指定一种可进行排序变量的方式非常有用,所以在Go 1.21的cmp
包中定义了这个Ordered
接口。该包还定义了两个比较函数。Compare
函数根据第一个参数是否小于、等于或大于第二个参数返回-1, 0或1,而Less
函数在第一个参数小于第二个参数时返回true
。
将同时具有类型元素和方法元素的接口用作类型参数完全合法。例如,可以指定一种类型的底层类型必须为int
并且具备String() string
方法:
type PrintableInt interface {
~int
String() string
}
注意Go会允许我们声明其实无法实例化的类型参数接口。如果在PrintableInt
中把~int
换成了int
,就不会有满足的有效类型,因为int
不带方法。这样不好,但编译器会进行补救。如果声明了带这种类型参数的类型或函数,企图使用时会导致编译错误。假设声明了这些类型:
type ImpossiblePrintableInt interface {
int
String() string
}
type ImpossibleStruct[T ImpossiblePrintableInt] struct {
val T
}
type MyInt int
func (mi MyInt) String() string {
return fmt.Sprint(mi)
}
虽然无法实例化ImpossibleStruct
,编译器对这些声明不会报错。不过在使用ImpossibleStruct
时,编译器就会报错了。以下代码:
s := ImpossibleStruct[int]{10}
s2 := ImpossibleStruct[MyInt]{10}
会报编译时错误:
int does not implement ImpossiblePrintableInt (missing String method)
MyInt does not implement ImpossiblePrintableInt (possibly missing ~ for
int in constraint ImpossiblePrintableInt)
可在The Go Playground 或第8章的GitHub代码库的sample_code/impossible目录下测试这段代码。
除了内置的原生类型外,类型名也可以是切片、字典、数组、通道、结构体甚至函数。它最大的用处是用于保证类型参数具有指定底层类型或一到多个方法。
类型推导和泛型
就像在使用:=
时支持类型推导一样,在调用泛型函数时Go同样支持类型推导。可在上面对Map
、Filter
和Reduce
调用中看出。有些场景无法进行类型推导(如类型参数仅用作返回值)。这时,必须指定所有的参数类型。下面的代码演示了无法进行类型推导的场景:
type Integer interface {
int | int8 | int16 | int32 | int64 | uint | uint8 | uint16 | uint32 | uint64
}
func Convert[T1, T2 Integer](in T1) T2 {
return T2(in)
}
func main() {
var a int = 10
b := Convert[int, int64](a) // 无法推导返回类型
fmt.Println(b)
}
可在The Go Playground 或第8章的GitHub代码库的sample_code/type_inference目录下测试这段代码。
类型元素限定常量
类型元素也可指定哪些常量可赋值给泛型变量。和运算符一样,常需要对类型元素中的所有类型名有效。没有常量可同时赋值给Ordered
中列出的所有类型,因此无法将一个常量赋值给该泛型类型的变量。如果使用Integer
接口,以下代码无法编译通过,因为不能将1,000赋值给8位的整型:
// INVALID!
func PlusOneThousand[T Integer](in T) T {
return in + 1_000
}
但下面的就是有效的:
// VALID
func PlusOneHundred[T Integer](in T) T {
return in + 100
}
组合泛型函数和泛型数据结构
回到二叉树示例,来看如何使用所学的知识生成适用所有实体类型的树。
核心在于理解该树需要一个泛型函数,可比较两个值给出排序:
type OrderableFunc [T any] func(t1, t2 T) int
有了OrderableFunc
,我们就可以稍稍修改树的实现。首先将其分成两种类型,Tree
和Node
:
type Tree[T any] struct {
f OrderableFunc[T]
root *Node[T]
}
type Node[T any] struct {
val T
left, right *Node[T]
}
通过构造函数构造一个新Tree
:
func NewTree[T any](f OrderableFunc[T]) *Tree[T] {
return &Tree[T]{
f: f,
}
}
Tree
的方法非常简单,因为它调用Node
来完成任务:
func (t *Tree[T]) Add(v T) {
t.root = t.root.Add(t.f, v)
}
func (t *Tree[T]) Contains(v T) bool {
return t.root.Contains(t.f, v)
}
Node
的Add
和Contains
方法与之前的非常类似。唯一的区别是传递了用于排序元素的函数:
func (n *Node[T]) Add(f OrderableFunc[T], v T) *Node[T] {
if n == nil {
return &Node[T]{val: v}
}
switch r := f(v, n.val); {
case r <= -1:
n.left = n.left.Add(f, v)
case r >= 1:
n.right = n.right.Add(f, v)
}
return n
}
func (n *Node[T]) Contains(f OrderableFunc[T], v T) bool {
if n == nil {
return false
}
switch r := f(v, n.val); {
case r <= -1:
return n.left.Contains(f, v)
case r >= 1:
return n.right.Contains(f, v)
}
return true
}
现在我们需要匹配OrderedFunc
定义的函数。所幸我们已经见过一个:cmp
包中的Compare
。在对Tree
使用它时是这样:
t1 := NewTree(cmp.Compare[int])
t1.Add(10)
t1.Add(30)
t1.Add(15)
fmt.Println(t1.Contains(15))
fmt.Println(t1.Contains(40))
对于结构体,有两种选项。可以编写一个函数:
type Person struct {
Name string
Age int
}
func OrderPeople(p1, p2 Person) int {
out := cmp.Compare(p1.Name, p2.Name)
if out == 0 {
out = cmp.Compare(p1.Age, p2.Age)
}
return out
}
然后在创建树进传递该函数:
t2 := NewTree(OrderPeople)
t2.Add(Person{"Bob", 30})
t2.Add(Person{"Maria", 35})
t2.Add(Person{"Bob", 50})
fmt.Println(t2.Contains(Person{"Bob", 30}))
fmt.Println(t2.Contains(Person{"Fred", 25}))
不使用函数,我们了可以为NewTree
提供一个方法。在方法也是函数中我们讨论过,可以使用方法表达式来将方法看作函数。下面上手操作。首先编写方法:
func (p Person) Order(other Person) int {
out := cmp.Compare(p.Name, other.Name)
if out == 0 {
out = cmp.Compare(p.Age, other.Age)
}
return out
}
然后使用该方法:
t3 := NewTree(Person.Order)
t3.Add(Person{"Bob", 30})
t3.Add(Person{"Maria", 35})
t3.Add(Person{"Bob", 50})
fmt.Println(t3.Contains(Person{"Bob", 30}))
fmt.Println(t3.Contains(Person{"Fred", 25}))
可在The Go Playground 或第8章的GitHub代码库的sample_code/generic_tree目录下测试这段代码。
再谈可比较类型
在接口可比较一节中我们学到,接口中也是Go中一种可比较类型。这也就表示在对接口类型变量使用==
和!=
时要小心。如果接口的底层类型不可比较,代码会在运行时panic。
这个坑在使用带泛型的可比较接口时依然存在。假设我们定义了一个接口以及一些实现:
type Thinger interface {
Thing()
}
type ThingerInt int
func (t ThingerInt) Thing() {
fmt.Println("ThingInt:", t)
}
type ThingerSlice []int
func (t ThingerSlice) Thing() {
fmt.Println("ThingSlice:", t)
}
还需要定义一个泛型函数仅接收可比较的值:
func Comparer[T comparable](t1, t2 T) {
if t1 == t2 {
fmt.Println("equal!")
}
}
调用带类型为int
或ThingerInt
的变量的函数完全合法:
var a int = 10
var b int = 10
Comparer(a, b) // prints true
var a2 ThingerInt = 20
var b2 ThingerInt = 20
Comparer(a2, b2) // prints true
编译器不允许我们调用变量类型为ThingerSlice
(或[]int
)的函数:
var a3 ThingerSlice = []int{1, 2, 3}
var b3 ThingerSlice = []int{1, 2, 3}
Comparer(a3, b3) // compile fails: "ThingerSlice does not satisfy comparable"
但所调用的变量类型为Thinger
时完全合法。如果使用ThingerInt
,代码可正常编译、运行:
var a4 Thinger = a2
var b4 Thinger = b2
Comparer(a4, b4) // prints true
但也可以将ThingerSlice
赋值给Thinger
类型的变量。这时会出问题:
a4 = a3
b4 = b3
Comparer(a4, b4) // compiles, panics at runtime
编译器允许我们构建这段代码,但运行后程序会panic(参见panic和recover一节了解更多信息),消息为panic: runtime error: comparing uncomparable type main.ThingerSlice
。可在The Go Playground 或第8章的GitHub代码库的sample_code/more_comparable目录下测试这段代码。
在关可比较类型和泛型交互以及为何做出这种设计决策的更多技术细节,请阅读Go团队Robert Griesemer的博客文章All your comparable types。
未实现的功能
Go仍是一种小型且聚焦的编程语言,Go对泛型的实现并未包含部分在其它语言泛型中存在的特性。下面是一些Go泛型尚未实现的特性。
虽然我们可以构建一个同时能处理自定义和内置类型的树,但在Python、Ruby和C++中处理的方法却不同。它们有运算符重载,允许用户自定义类型指定运算符的实现。 Go没有添加这种特性。也就意味着我们不能使用range
遍历自定义容器类型,也不能对其使用[]
进行索引。
没添加运算符重载有一些原因。其一是Go语言中有极其大量的运算符。Go也不支持函数或方法重载,那就需要为不同的类型指定不同的运算函数。此外,重载的代码会不易理解,因为开发人员会为符号巧立各种含义(在C++中,<<
对一些类型表示按位左移,而对另一些类型则在左侧值的右侧写值)。Go努力避免这类易读性问题。
另一个未实现的有用特性是,Go的泛型实现对方法没有附加类型参数。回看Map/Reduce/Filter
函数,你可能觉得它们可像方法那样使用,如:
type functionalSlice[T any] []T
// THIS DOES NOT WORK
func (fs functionalSlice[T]) Map[E any](f func(T) E) functionalSlice[E] {
out := make(functionalSlice[E], len(fs))
for i, v := range fs {
out[i] = f(v)
}
return out
}
// THIS DOES NOT WORK
func (fs functionalSlice[T]) Reduce[E any](start E, f func(E, T) E) E {
out := start
for _, v := range fs {
out = f(out, v)
}
return out
}
你以为可以这样用:
var numStrings = functionalSlice[string]{"1", "2", "3"}
sum := numStrings.Map(func(s string) int {
v, _ := strconv.Atoi(s)
return v
}).Reduce(0, func(acc int, cur int) int {
return acc + cur
})
可惜对于函数式编程的拥趸们,并不能这样用。我们不能做链式方法调用,而要嵌套函数调用或使用更易读一次调用一次函数的方式,将中间值赋给变量。类型参数提案中详细讨论了未支持参数化方法的原因。
没有可变类型参数。在可变参数和切片一节中讨论到,要实现接收可变数量参数的函数,需要指定最后一个参数,其类型以...
开头。比如,无法对可变参数指定某种类型模式,像可交替的string
和int
。所有的可变变量必须为同一种声明类型,是不是泛型皆可。
Go泛型未实现的其它特性就更加晦涩些了。有:
-
特化(Specialization)
函数或方法可通过泛型版本外的一个或多个指定类型版本进行重载。因Go语言没有重载,这一特性不在考虑范围内。
-
柯里化(Currying)
允许我们通过指定某些类型参数根据另一个泛型函数或类型部分实例化函数。
-
元编程
允许我们指定在编译时运行的代码并生成运行时运行的代码。
地道的Go和泛型
添加泛型显然会改变一些地道使用Go的建议。使用float64
来表示所有的数值类型的时代结束了。应当使用any
来代替interface{}
表示数据结构或函数参数中未指定的类型。可以用一个点函数处理不同的切片类型。但不要觉得要马上使用类型参数切换掉所有的代码。在新设计模式发明和深化的同时老代码依然正常可用。
现在判断泛型对性能的长期影响还为时尚早。在写本文时,它对编译时间并没有影响。Go 1.18的编译器要慢于之前的版本,但Go 1.20的编译器解决了这一问题。
有一些关于泛型对运行时间影响的影响。Vicent Marti写了一篇深入的文章,探讨了一些导致代码变慢的泛型案例并详细讲解了产生这一问题的实现细节。相反,Eli Bendersky写了一篇博客文章说明泛型让排序算法变快了。
一般来说,不要期望将带接口参数的函数修改为泛型类型参数的函数能提升性能。比如,将下面的小函数:
type Ager interface {
age() int
}
func doubleAge(a Ager) int {
return a.age() * 2
}
转化为:
func doubleAgeGeneric[T Ager](a T) int {
return a.age() * 2
}
会使得该函数在Go 1.20变慢约30%。(对于大型函数,没有显著的性能区别)。可以使用第8章的GitHub代码库的sample_code/perf directory目录下代码进行基准测试。
使用过其它语言泛型的开发者可能会感到意外。比如在C++中,编译器使用抽象数据类型的泛型来将运行时运算(确定所使用的实体类型)转化为编译时运算,为每种实体类型生成独立的函数。这会让二进制变大,但也让其变快。Vicent在博客文章中提到,当前的Go编译器仅为不同的底层类型生成独立函数。此外,所有指针类型共享同一个生成函数。为区分传递给共享生成函数的类型,编译器添加了额外的运行时查询。这会减慢性能。
随着Go未来版本中泛型实现渐趋成熟,运行时性能也会提升。目标并没有改变,还是要编写满足需求且易维护的快速运行代码。使用基准测试一节中讨论的基准测试和性能测试工具来度量和提升你的代码。
向标准库添加泛型
Go 1.18刚发布泛型时是很保守的。在全局添加了any
和comparable
接口,但并未在标准库中做出支持泛型的API调整。只做出了样式变化,将大部分标准库中的interface{}
改成了any
。
现在Go社区更适应了泛型,我们也看到了更多的变化。从Go 1.21起,标准库中包含了一些函数,使用泛型实现切片、字典和并发的常用算法。在复合类型一文中我们讲到了slices
和maps
包中的Equal
和EqualFunc
函数。这些包中的其它函数简化了切片和字典操作。slices
包中的Insert
、Delete
和DeleteFunc
函数让开发展不必构建极其复杂的切片处理代码。maps.Clone
函数利用Go Runtime来提供更快速的方式,来创建字典的浅拷贝。在代码精确地只运行一次一节中,我们学到sync.OnceValue
和sync.OnceValues
,它们使用泛型来构建只运行一次并返回一到两个值的函数。推荐使用这些包中的函数,而不要自己去实现。未来版本的标准库还会包含更多用到泛型的函数和类型。
解锁未来特性
泛型可能是其它未来特性的基础。一个可能是sum types。就像类型元素用于指定可替换类型参数的类型一样,和类型可用于变量参数中的接口。这会出现一些有趣的特性。如今Go在JSON的常见场景存在问题:其字段可以是单个值也可是值列表。即使是有泛型,处理这种情况的唯一方式是装饰字段类型设为any
。添加和类型可让我们创建指定字段可为字符串、字符串切片及其它类型的接口。然后类型switch可以枚举每种有效类型,提升类型案例。指定类型边界集的能力可以让现代语言(包括Rust和Swift)使用和类型替代枚举。而Go当前在枚举特性上存在不足,这会成为一种有吸引力的解决方案,但需要时间来评估和探讨这些想法 。
小结
本文中我们学习了泛型以及如何使用泛型来简化代码。对于Go来说泛型还处于早期除非。有它伴随Go语言不忘初心的成长还是很让人激动的。