Go泛型参考

0x00 前言

泛型已经确定将在 go 1.18 里发布，预计到 22 年 2 月份就可以使用到 release 版本的 go 泛型了。虽然官方并不建议大家在第一时间去把内部组件升级到泛型版本，但是提前了解下泛型对我们使用上有什么影响还是很有必要的。个人认为 Go 泛型是 go 在 1.11 支持 go mod 之后对语言层面最大的一次变动。早在 go 1.17 时，在 master 分支里就能看到 go 泛型的身影，只是默认不开启，即 cmd/compile 的 -G flag 默认值为 0。

0x01 泛型

1.规则

下面看一组基本概念，go 泛型实现规则：

函数使用方括号，接收类型参数列表，形式如 func F[T any](p T) {...}
- 可以定义每个类型参数的约束 func F[T Constraint] (p T){...}
类型参数可以被常规参数和函数体使用
可以定义类型参数列表，形式如type M[T any] []T
类型约束是接口类型
any为允许任何类型的类型约束
类型限制
- 任意类型：T限制为该类型
- 近似类型：~T限制为基础类型为T，如~int对type Enum int也生效
- union 类型：T1 | T2 | ....限制为任意列出的类型
泛型函数只能使用所有类型约束允许的操作
使用泛型函数或类型需要传递类型参数
类型推断允许在常见情况下省略函数调用的类型参数

如果你使用过其他的泛型语言，从上面可以看到 go 不支持的特性：

没有协变和逆变，简化了泛型概念
没有元编程支持，反射包不会改变
只通过接口类型约束类型参数的行为
缺少操作符支持
没有可变类型参数支持

2.包变动

新增constraints包，用于常见的类型参数集合，类型定义如下：

type Signed interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
}

type Unsigned interface {
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

type Integer interface {
	Signed | Unsigned
}

type Float interface {
	~float32 | ~float64
}

type Complex interface {
	~complex64 | ~complex128
}

type Ordered interface {
	Integer | Float | ~string
}

3.使用

any 约束

any和interface{}在含义上是一致的，都能表示任意类型。其实像rune是int32的别名一样，any也是interface{}的别名，只是从语义上更容易理解，写法上也更规范。因此any 其实不是一个关键字。*该规范可以参考这个链接

因此下面两种写法，含义也是一样的，只是any语义更清楚：

func Print1[T any](s []T) {
    for _, v := range s{
        fmt.Println(v)
    }
}
// ----
func Print2[T interface{}] (s []T) {
	// print...
}

多个类型参数

在一个函数接收多个参数时，定义一个或多个类型参数之前是有区别的。像下面Print1里s1和s2可以是两个不同类型的切片，但Print2里必须是相同元素类型的切片。

func Print1[T1, T2 any] (s1 []T1, s2 []T2) {
	//...
}

func Print2[T any](s1 []T, s2 []T) {
    //...
}

泛型类型

除了泛型函数外，我们还可以定义泛型类型。像定义普通类型一样，泛型的定义也是使用type关键字：

// Vector 是任意元素类型的切片
type Vector [T any] []T

在实际使用中就可以通过制定T的类型来实例化具体类型，例如

var v Vector[int]
// or
v := Vector[int]{}

同时，泛型类型也可以像普通类型一样有方法，方法的接收器类型必须声明与类型定义中相同的类型。

// 向v中添加元素
func (v *Vector[T]) Push(x T) {
    *v = append(*v, x)
}

类型集合

像constaraints包里定义的那样，使用类似接口定义的形式，可以将一堆类型组合起来，定义一个新的类型:(这里 go 出现了一种新的语法) ~T 含义是所有基础类型为T的类型集合，例如

type AliasString = string
type StringEnum  string
type UserEnum StringEnum

// AnyString包含了上面StringEnum、AliasString、UserEnum等
// 从string派生出来的string类型
type AnyString interface{
	~string
}

注意，如果T是类型参数或接口类型，不是基础类型，~T与T一起使用时，将报错：

type MyString string

type AnyString interface{
	~string
}

// 下面两个定义无效

type InvalidString interface {
	~MyString // 因为MyString的基础类型是string，不是MyString
}

type InvalidSlice [T any] interface {
	~T // 因为T是一个类型参数，不是基础类型
}

可比较类型

为了判断泛型元素是否有可比较性，go 引入新的类型约束comparable，对应为==和!=操作符。可以再结构、数组和接口类型里使用。例如

// 获取x在s中的位置索引，如果未找到，返回-1
func Index[T comparable](s []T, x T) int {
    for i, v := range s {
        //v和x具有可比性
        if v == x {
            return i
        }
    }
    return -1
}

同时，compare也可以在接口约束中使用。

// 任意具有可比性并且实现了Hash的方法
type ComparableHasher interface {
    comparable
    Hash() uintptr
}

类型推断

在许多情况下，可以借助 go 类型推断特性，避免显式的写出部分或全部参数。在 go 编译器不知道怎么从已知类型推断出未知类型时，会报编译错误。

//定义了下面的泛型函数
func Map[F, T any](s []F, f func(F) T) []T {
	x := make([]T, len(s))
	for i,v := range s {
		x[i] = f(v)
	}
	return x
}

// 已知类型
var s []int
f := func(i int)int64 { return int64(i)}

//可以通过下面这些方式调用
var r []int64
r = Map[int, int64](s, f) // 明确两个参数
r = Map[int](s, f) // 明确第一个参数，推断第二个
r = Map(s, f) // 不指定任意参数，全部走类型推断

反射

go 官方不建议以任何方式更改反射包。当一个类型或函数在被实例化之后，所有的泛型都会被变成非泛型类型或函数。同时，非泛型代码也不可能在未实例化的情况下引用泛型代码，因此目前不支持获取未实例化的泛型类型或函数的反射信息。

0x02 实践

1.双向链表

如果使用interface来实现双向链表的编写，那很多地方就需要去做类型转换。在使用时就很难受，尤其 go 的类型断言用起来很麻烦。而使用泛型，就解决了这个问题。

package main

import "fmt"

type List[T comparable] struct {
	head, tail *node[T]
	len int
}

// 定义节点
type node[T comparable] struct {
	data T
	prev *node[T]
	next *node[T]
}


func (l *List[T]) IsEmpty() bool {
	return l.head == nil && l.tail == nil
}

//Add 在链表头部添加元素
func (l *List[T]) Add(data T)  {
    n := &node[T]{ //不能直接使用node{}
		data: data,
		prev: nil,
		next: l.head,
	}
	if l.IsEmpty() {
		l.head = n
		l.tail = n
	}
	l.head.prev = n
	l.head = n
}

//Push 在链表尾部添加元素
func (l *List[T]) Push(data T)  {
	n := &node[T]{
		data: data,
		prev: l.tail,
		next: nil,
	}
	if l.IsEmpty() {
		l.head = n
		l.tail = n
	}
	l.tail.next = n
	l.tail = n
}

//Contains 判断是否包含指定元素
func (l *List[T]) Contains(data T) bool {
	for p:= l.head; p != nil; p = p.next {
		if p.data == data {
			return true
		}
	}
	return false
}

//Remove 移除指定元素
//用到了比较，所有需要comparable约束
func (l *List[T]) Remove(data T)  {
	for p:= l.head; p != nil; p = p.next {
		if p.data != data {
			continue
		}
		if p == l.head {
			l.head = p.next
		}
		if p == l.tail {
			l.tail = p.prev
		}
		if p.prev != nil {
			p.prev.next = p.next
		}
		if p.next != nil {
			p.next.prev = p.prev
		}
		return
	}
}

//Print 打印所有元素
func (l *List[T]) Print()  {
	if l.IsEmpty() {
		fmt.Println("link list is empty")
		return
	}

	for p := l.head; p != nil ; p = p.next {
		fmt.Printf("[%v] ->", p.data)
	}
	fmt.Println("nil")
}

执行测试

func main() {
	l := List[int64]{}
	l.Add(100)
	l.Add(200)
	l.Print()
	fmt.Println("contains 100 :", l.Contains(100))
	l.Remove(100)
	fmt.Println("contains 100 :", l.Contains(100))
	l.Add(2)
	l.Add(50)
	l.Push(70)
	l.Print()
}

执行结果

$ go build linklist.go && ./linklist
[200] ->[100] ->nil
contains 100 : true
contains 100 : false
[50] ->[2] ->[200] ->[70] ->nil

2.maps

go 已经正式提交了支持泛型的 maps 包，详细见可以看下其实现

// Package maps defines various functions useful with maps of any type.
package maps

// Keys returns the keys of the map m.
// The keys will be in an indeterminate order.
func Keys[M ~map[K]V, K comparable, V any](m M) []K {
	r := make([]K, 0, len(m))
	for k := range m {
		r = append(r, k)
	}
	return r
}

// Values returns the values of the map m.
// The values will be in an indeterminate order.
func Values[M ~map[K]V, K comparable, V any](m M) []V {
	r := make([]V, 0, len(m))
	for _, v := range m {
		r = append(r, v)
	}
	return r
}

//...more

在正常使用 map 时，得到的是interface{}。使用泛型后，就能很方便的获取 map 里定义的字段类型例如:

func main() {
	m := make(map[string]string)
	m["key1"] = "val1"
	m["key2"] = "val2"
	fmt.Println("keys", strings.Join(maps.Keys(m), ",")) //可以直接join，不再需要类型转换
	fmt.Println("vals", strings.Join(maps.Values(m), ","))
}

3.stream

java8 里 stream 对集合对象的操作非常便利，对业务开发人员对数据的类型转换、处理操作又是再正常不过的需求，但 go 里受限于泛型的确实，已有的 stream 包使用也不友好。参考 java stream 里提供的部分操作:

filter //过滤流中某些元素
skip(n)、limit(n) //跳过n个、保留n个元素
map //遍历每个元素，生成新的流
flatMap // 将所有流打平
reduce //组合操作，将结果传入下次迭代，生成最终结果
allMatch、noneMatch、anyMatch//匹配操作
min、max、count//聚合操作
collect //类型转换
forEach //遍历每个元素

下面让我看下在 go 里的实现一个简易的stream操作

// 声明stream类型
type Stream[T any] struct {
	slice []T
}

// Of 生成新的stream流
func Of[T any](slice []T) *Stream[T]  {
	return &Stream[T]{slice: slice}
}

// Filter 过滤元素，结果为true时保留，否则过滤
func (s *Stream[T]) Filter(predicate func(T) bool) *Stream[T]  {
	filtered := []T{}
	for _, item := range s.slice {
		if predicate(item) {
			filtered = append(filtered, item)
		}
	}
	s.slice = filtered
	return s
}

// Map 遍历stream，调用predicate生成新的stream流
func Map[T any,R any] (s *Stream[T], predicate func(T)R) *Stream[R] {
	s2 := []R{}
	for _, item := range s.slice {
		s2 = append(s2, predicate(item))
	}
	return Of(s2)
}

// Reduce 遍历stream，将predicate的结果迭代传入predicate中
func Reduce[T any, R any] (s *Stream[T], predicate func(T, R)R) R {
  	var result R
	for _, item := range s.slice {
		result = predicate(item, result)
	}
	return result
}

// ForEach 遍历stream
func (s *Stream[T]) ForEach(predicate func(T)) {
	for _, item := range s.slice {
		predicate(item)
	}
}

我们实现了简单的 stream 流操作，下面一起来看下使用效果：和常见的 go stream 实现最大的区别就是少了很多类型转换。如果结合内置函数，使用上会更方便。

func main()  {
	nums := []int{1,2,3,4,5,6,7}

	stream := Of(nums) // 创建stream流

    //MapReduce，将nums每个元素迭代再依次叠加
	result := Reduce(
		Map(stream, func(t int) int {
		return t*t
	}), func(t int, r int) int {
		fmt.Println(t, r)
		return t+r
	})
	fmt.Println("reduce:", result)

    //取偶数
	s2 := stream.Filter(func(val int) bool {
		return val % 2 == 0
	})

    //翻倍再转string，再遍历
	Map(s2, func(val int) string {
		return strconv.Itoa(val *2)
	}).ForEach(func(val string) {
		fmt.Println("val:", val)
	})
}

上面实现的 stream 没有实现并发操作，如果结合goroutine和channel，则可以实现真正的并发流处理。

0x03 其他

go 除泛型后编译会变慢吗？

详细见 Go1.18 编译慢了近 20%?

和 java 语言比较有什么区别?

java 通过类型通配符(List<? extends Number>, List<? super Number>)实现协变和逆变，go 里没有类似的概念。另外 java 泛型实现时做了类型擦除，go 的类型设计则没有，所有元数据都可以保留在编译类型信息里。

Go 泛型有哪些限制?

Go 编译器目前无法处理泛型函数或方法中的类型声明。预计在 Go 1.19 中提供对此功能的支持(详细参考)

例如上面stream的例子中, map和reduce的实现，并没有用 struct 方法的形式来实现，就是这个原因：

func (s *Stream[T]) Filter[R any](predicate func(T) R) *Stream[T]  {
}

type predicate func[T, R any](T) R

上面的方法会编译失败:

./stream.go: methods cannot have type parameters
./stream.go: syntax error: function type cannot have type parameters

怎样了解泛型最新的进展？

可以去 go github 里的讨论区或者 issue 里找有关泛型的已通过的提案或者讨论。例如 https://github.com/golang/go/issues?q=is%3Aopen+is%3Aissue+label%3Agenerics+label%3AProposal-Accepted

0xff 参考

go type parameters proposal > go 泛型新方案-鸟窝 > generics-next-step > why generics