[译] Range Over Function Types

在 Go 1.22 中作为试验特性发布,在 Go 1.23 中正式发布。我们可以在 for 循环的 range 子句中使用迭代器函数。就在前几天,官方也发布了 Range over Function Types 的教程。

Ian Lance Taylor
in 20 August 2024


Go 1.23版本中函数类型范围遍历的新特性介绍

这是 Ian 在2024年GopherCon大会上演讲的博客文章版本,下面开始正文(文章较长但干货真的很多,读完会对迭代器函数的用法有新的理解)。

在 Go 1.23版本中,我们引入了一个新的语言特性:对函数类型进行范围遍历(Range over function types)。这篇博客文章将解释我们为什么要添加这个新特性,它究竟是什么,以及如何使用它。

WHY?

自 Go 1.18 版本以来,我们就能够编写新的泛型容器类型。例如,让我们实现一个非常简单的 Set 类型,一个基于 map 实现的泛型类型。

1
2
3
4
5
6
7
8
9
// Set 保存一组元素。
type Set[E comparable] struct {
m map[E]struct{}
}

// New 返回一个新的[Set]。
func New[E comparable]() *Set[E] {
return &Set[E]{m: make(map[E]struct{})}
}

自然地,一个 set 类型有添加元素的方法和检查元素是否存在的方法。

1
2
3
4
5
6
7
8
9
10
// Add 向set添加一个元素。
func (s *Set[E]) Add(v E) {
s.m[v] = struct{}{}
}

// Contains 报告一个元素是否在set中。
func (s *Set[E]) Contains(v E) bool {
_, ok := s.m[v]
return ok
}

还需要一个函数来返回两个集合的并集。

1
2
3
4
5
6
7
8
9
10
11
12
13
// Union 返回两个set的并集。
func Union[E comparable](s1, s2 *Set[E]) *Set[E] {
r := New[E]()
// 注意for/range在内部Set字段m上。
// 我们正在遍历s1和s2中的map。
for v := range s1.m {
r.Add(v)
}
for v := range s2.m {
r.Add(v)
}
return r
}

让我们花一点时间看看 Union 函数的实现。为了计算两个集合的并集,我们需要一种方法来获取每个集合中的所有元素。在这段代码中,我们使用了一个 for/range 语句来遍历 set 类型的未导出字段。这只在 Union 函数定义在set包中时才有效。

但是,有很多原因可能会有人想要遍历集合中的所有元素。这个 set 包必须为其用户提供一些方法来做到这一点。

这应该怎么实现呢?

Push Set 元素

一种方法是提供一个 Set 方法,该方法接受一个函数,并对 Set 中的每个元素调用该函数。我们将这称为 Push,因为 Set 将每个值推送到函数中。如果函数返回 false,我们停止调用它。

1
2
3
4
5
6
7
func (s *Set[E]) Push(f func(E) bool) {
for v := range s.m {
if !f(v) {
return
}
}
}

在 Go 标准库中,我们看到这种通用模式被用于 sync.Map.Range 方法、flag.Visit 函数和 filepath.Walk 函数等场景。这是一个通用模式,并非完全相同的模式;实际上,这三个例子的工作原理并不完全相同。

这就是使用 Push 方法打印 Set 中所有元素的样子:你用一个函数调用 Push,该函数对元素执行你想要的操作。

1
2
3
4
5
6
func PrintAllElementsPush[E comparable](s *Set[E]) {
s.Push(func(v E) bool {
fmt.Println(v)
return true
})
}

拉取 Set 元素

另一种遍历 Set 元素的方法是返回一个函数。每次调用该函数时,它将从 Set 中返回一个值,以及一个布尔值,报告该值是否有效。当循环遍历完所有元素时,布尔结果将为 false。在这种情况下,我们还需要一个停止函数,当不再需要更多值时可以调用它。

这个实现使用了一个通道对,一个用于集合中的值,一个用于停止返回值。我们使用一个 goroutine 在通道上发送值。next 函数通过从元素通道读取来从集合中返回一个元素,stop 函数通过关闭停止通道来告诉 goroutine 退出。我们需要 stop 函数以确保当不再需要更多值时 goroutine 能够退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func (s *Set[E]) Pull() (func() (E, bool), func()) {
ch := make(chan E)
stopCh := make(chan bool)

go func() {
defer close(ch)
for v := range s.m {
select {
case ch <- v:
case <-stopCh:
return
}
}
}()

next := func() (E, bool) {
v, ok := <-ch
return v, ok
}

stop := func() {
close(stopCh)
}

return next, stop
}

标准库中没有任何东西完全以这种方式工作。runtime.CallersFramesreflect.Value.MapRange 有些相似,尽管它们返回的是带有方法的值,而不是直接返回函数。

这就是使用 Pull 方法打印 Set 中所有元素的例子。你调用 Pull 来获取一个函数,并在 for 循环中反复调用该函数。

1
2
3
4
5
6
7
func PrintAllElementsPull[E comparable](s *Set[E]) {
next, stop := s.Pull()
defer stop()
for v, ok := next(); ok; v, ok = next() {
fmt.Println(v)
}
}

标准化方法

现在我们已经看到了两种不同的方法来遍历一个集合的所有元素。不同的 Go 包使用这些方法和几种其他方法。这意味着,当你开始使用一个新的 Go 容器包时,你可能需要学习一种新的循环机制。同时,这意味着我们不能编写一个函数来与几种不同类型的容器一起工作,因为容器类型将以不同的方式处理循环。

我们希望通过为容器遍历开发标准方法来改善 Go 生态系统。

迭代器

这当然是许多编程语言中出现的问题。

1994 年首次出版的流行书籍《设计模式》将此描述为迭代器模式。你使用迭代器来“提供一种顺序访问聚合对象元素的方法,而不需要暴露其底层表示。”这里所谓的聚合对象就是我一直所说的容器。聚合对象或容器只是保存其他值的值,比如我们一直在讨论的 Set 类型。

像编程中的许多想法一样,迭代器可以追溯到 20 世纪 70 年代 Barbara Liskov 开发的 CLU “CLU”) 语言。

今天,许多流行的语言以这样或那样的方式提供迭代器,包括但不限于 C++、Java、Javascript、Python和Rust。

然而,在 1.23 版本之前,Go 并没有。

For/range

正如我们所知,Go 有内置于语言的容器类型:切片、数组和 map。它有一种访问这些值的元素的方法,而不需要暴露其底层表示:for/range语句。for/range语句适用于 Go 的内置容器类型(以及字符串、channel,以及从 Go 1.22 开始的 int)。

for/range 语句是迭代,但它不是今天流行语言中出现的迭代器。尽管如此,能够使用 for/range 来迭代像Set类型这样的用户定义容器将是很好的。

然而,在 1.23 版本之前的 Go 并不支持这一点。

此版本中的改进

对于 Go 1.23,我们决定支持对用户定义的容器类型进行 for/range,并支持迭代器的标准化形式。

我们扩展了 for/range 语句,使其支持对函数类型进行范围遍历。我们将在下面看到这如何帮助循环遍历用户定义的容器。

我们还添加了标准库类型和函数,以支持使用函数类型作为迭代器。标准迭代器的定义让我们能够编写与不同容器类型平滑协作的函数。

范围遍历(部分)函数类型

改进的 for/range 语句不支持任意函数类型。截至 Go 1.23,它现在支持对接受单个参数的函数进行范围遍历。这个单一参数本身必须是一个函数,它接受零到两个参数并返回一个 bool;按照惯例,我们称之为 yield函数。

1
2
3
4
5
func(yield func() bool)

func(yield func(V) bool)

func(yield func(K, V) bool)

当我们谈到 Go 中的迭代器时,我们指的是具有这三种类型之一的函数。正如我们将在下面讨论的,标准库中还有另一种迭代器:拉取迭代器。当需要区分标准迭代器和拉取迭代器时,我们称标准迭代器为推送迭代器。这是因为,正如我们将看到的,它们通过调用 yield 函数来推送一系列值。

标准(推送)迭代器

为了使迭代器更易于使用,新的标准库包 iter 定义了两种类型:Seq 和 Seq2。这些是迭代器函数类型的名称,是可以与for/range语句一起使用的类型。Seq的名称是sequence(序列)的缩写,因为迭代器按顺序循环遍历一系列值。

1
2
3
4
5
6
7
package iter

type Seq[V any] func(yield func(V) bool)

type Seq2[K, V any] func(yield func(K, V) bool)

// 现在,没有Seq0

Seq 和 Seq2 之间的区别只是 Seq2 是一对序列,比如来自 map 的键和值。在这篇文章中,为了简单起见,我们将专注于 Seq,但我们所说的大部分也适用于 Seq2。

最容易通过一个例子来解释迭代器是如何工作的。这里 Set 方法 All 返回一个函数。

All 的返回类型是 iter.Seq[E],所以我们知道它返回一个迭代器。

1
2
3
4
5
6
7
8
9
10
// All 是对s中元素的迭代器。
func (s *Set[E]) All() iter.Seq[E] {
return func(yield func(E) bool) {
for v := range s.m {
if !yield(v) {
return
}
}
}
}

迭代器函数本身接受另一个函数作为参数,即 yield 函数。迭代器用集合中的每个值调用 yield 函数。在这个例子中,迭代器,由 Set.All 返回的函数,与我们之前看到的 Set.Push 函数非常相似。

这就是迭代器的工作原理:对于某些值序列,它们用序列中的每个值调用 yield 函数。如果 yield 函数返回 false,则不再需要更多的值,迭代器可以简单地返回,执行可能需要的任何清理工作。如果 yield 函数从不返回 false,则迭代器可以在用序列中的所有值调用 yield 之后简单地返回。

这就是它们的工作原理,但让我们承认,当你第一次看到这些时,你的第一反应可能是“这里有很多函数在飞来飞去。”你对此的看法并没有错。让我们关注两件事。

第一,一旦你越过这个函数代码的第一行,这个迭代器的实际实现实际上非常简单:用集合中的每个元素调用 yield,如果 yield 返回 false 则停止。

1
2
3
4
5
for v := range s.m {
if !yield(v) {
return
}
}

第二,使用这个真的很容易。你调用 s.All 来获取一个迭代器,然后你使用 for/range 来循环遍历s中的所有元素。for/range 语句支持任何迭代器。

1
2
3
4
5
func PrintAllElements[E comparable](s *Set[E]) {
for v := range s.All() {
fmt.Println(v)
}
}

在这种代码中,s.All 是一个返回函数的方法。我们调用 s.All,然后使用 for/range 来遍历它返回的函数。在这种情况下,我们可以将 Set.All 做成一个迭代器函数本身,而不是让它返回一个迭代器函数。然而,在某些情况下,这行不通,比如如果返回迭代器的函数需要接受一个参数,或者需要做一些设置工作。作为一种惯例,我们鼓励所有容器类型都提供一个返回迭代器的 All 方法,这样程序员就不必记住是直接遍历 All 还是调用 All 来获取一个可以遍历的值。他们总是可以做后者。

如果你仔细想想,你会看到编译器必须调整循环以创建一个 yield 函数传递给 s.All 返回的迭代器。在 Go 编译器和运行时有一些复杂性,使这变得高效,并正确处理像循环中的 break 或 panic 这样的事情。我们不会在这篇博客文章中涵盖这些内容。幸运的是,当涉及到实际使用这个特性时,实现细节并不重要。

拉取迭代器

现在我们已经看到了如何在 for/range 循环中使用迭代器。但一个简单的循环并不是使用迭代器的唯一方式。例如,有时我们可能需要并行地遍历两个容器。我们该怎么做呢?

答案是我们使用一种不同类型的迭代器:拉取迭代器。我们已经看到,一个标准迭代器,也称为推送迭代器,是一个接受 yield 函数作为参数的函数,并通过调用 yield 函数推送序列中的每个值。

拉取迭代器的工作方式正好相反:它是一个这样的函数,每次你调用它时,它都会从序列中拉取下一个值并返回它。

我们将重复两种迭代器之间的区别,以帮助你记住:

一个推送迭代器将序列中的每个值推送到yield函数。推送迭代器是 Go 标准库中的迭代器,并且直接被 for/range语句支持。
一个拉取迭代器的工作方式正好相反。每次你调用一个拉取迭代器时,它都会从序列中拉取另一个值并返回它。拉取迭代器不是直接被 for/range 语句支持的;然而,编写一个普通的 for 语句来遍历拉取迭代器是直接了当的。实际上,当我们看到使用 Set.Pull 方法时,我们已经看到了一个例子。

你可以自己编写一个拉取迭代器,但通常你不必这么做。新标准库函数 iter.Pull 接受一个标准迭代器,也就是说,一个推送迭代器的函数,并返回一对函数。第一个是一个拉取迭代器:一个每次被调用时都返回序列中的下一个值的函数。第二个是一个停止函数,当我们完成对拉取迭代器的使用时应该调用它。这就像我们之前看到的 Set.Pull 方法。

iter.Pull 返回的第二个函数,即停止函数,以防我们没有读取完整个序列。在一般情况下,推送迭代器,即传递给 iter.Pull 的参数,可能会启动 goroutines 或构建需要在迭代完成时清理的新数据结构。推送迭代器将在 yield 函数返回 false 时执行任何清理工作,这意味着不再需要更多的值。当与 for/range 语句一起使用时,for/range 语句将确保如果循环提前退出,无论是通过 break 语句还是其他任何原因,那么 yield 函数将返回 false。而使用拉取迭代器时,另一方面,没有办法强制 yield 函数返回 false,所以需要停止函数。

另一种说法是,调用停止函数将导致 yield 函数在被推送迭代器调用时返回 false。

严格来说,如果拉取迭代器返回 false 以表示它已经到达序列的末尾,你就不必调用停止函数,但通常简单地总是调用它会更简单。

以下是一个使用拉取迭代器并行遍历两个序列的示例。这个函数报告任意两个序列是否包含相同的元素,顺序也相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// EqSeq报告两个迭代器是否包含相同的
// 元素,顺序也相同。
func EqSeq[E comparable](s1, s2 iter.Seq[E]) bool {
next1, stop1 := iter.Pull(s1)
defer stop1()
next2, stop2 := iter.Pull(s2)
defer stop2()
for {
v1, ok1 := next1()
v2, ok2 := next2()
if !ok1 {
return !ok2
}
if ok1 != ok2 || v1 != v2 {
return false
}
}
}

函数使用 iter.Pull 将两个推送迭代器 s1 和 s2 转换为拉取迭代器。它使用 defer 语句确保我们在完成对它们使用后停止拉取迭代器。

然后代码循环,调用拉取迭代器检索值。如果第一个序列完成了,如果第二个序列也完成了,它返回 true,或者如果它没有完成,返回 false。然后它循环拉取下两个值。

和推送迭代器一样,Go 运行时有一些复杂性,使拉取迭代器高效,但这不影响实际使用 iter.Pull 函数的代码。

在迭代器上迭代

现在你知道了关于函数类型范围遍历和迭代器的所有事情。我们希望你享受使用它们!

尽管如此,还有一些值得提及的事情。

适配器

标准迭代器定义的一个优势是能够编写使用它们的标准适配器函数。

例如,这里有一个函数,它过滤一个值序列,返回一个新的序列。这个 Filter 函数接受一个迭代器作为参数,并返回一个新的迭代器。另一个参数是一个过滤器函数,它决定哪些值应该包含在 Filter 返回的新迭代器中。

1
2
3
4
5
6
7
8
9
10
11
12
13
// Filter 返回一个序列,其中包含 s 中
// 满足 f 返回 true 的元素。
func Filter[V any](f func(V) bool, s iter.Seq[V]) iter.Seq[V] {
return func(yield func(V) bool) {
for v := range s {
if f(v) {
if !yield(v) {
return
}
}
}
}
}

和之前的例子一样,函数签名在你第一次看到它们时看起来很复杂。一旦你超越了签名,实现就很简单了。

1
2
3
4
5
6
7
for v := range s {
if f(v) {
if !yield(v) {
return
}
}
}

代码遍历输入迭代器,检查过滤器函数,并用应该进入输出迭代器的值调用yield。

我们将在下面展示使用 Filter 的示例。

(Go标准库今天没有 Filter 的版本,但未来版本可能会添加。)

二叉树

作为推送迭代器对容器类型循环遍历的便利性的一个例子,让我们考虑这个简单的二叉树类型。

1
2
3
4
5
// Tree是一个二叉树。
type Tree[E any] struct {
val E
left, right *Tree[E]
}

我们不会展示将值插入树的代码,但自然应该有某种方法来遍历树中的所有值。

事实证明,如果迭代器代码返回一个 bool,迭代器代码会更容易编写。由于 for/range 支持的函数类型不返回任何内容,这里的 All 方法返回一个小型函数字面量,它调用迭代器本身,这里称为 push,并忽略 bool 结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// All返回t中值的迭代器。
func (t *Tree[E]) All() iter.Seq[E] {
return func(yield func(E) bool) {
t.push(yield)
}
}

// push将所有元素推送到yield函数。
func (t *Tree[E]) push(yield func(E) bool) bool {
if t == nil {
return true
}
return t.left.push(yield) &&
yield(t.val) &&
t.right.push(yield)
}

push 方法使用递归来遍历整棵树,对每个元素调用 yield。如果 yield 函数返回false,该方法
会一直返回 false。否则,它只是在迭代完成时返回一次。

这展示了使用这种迭代器方法遍历甚至是复杂数据结构有多么直接。没有必要维护一个单独的栈来记录树内的位置;我们可以使用 goroutine 调用栈为我们做这件事。

新的迭代器函数

在 Go 1.23 中,slices 和 maps 包中也新增了一些与迭代器一起工作的功能。

以下是 slices 包中的新函数。All 和 Values 是返回 slice 元素迭代器的函数。Collect 从迭代器中提取值,并返回包含这些值的 slice。查看其他函数的文档。

1
2
3
4
5
6
7
8
9
10
All([]E) iter.Seq2[int, E]
Values([]E) iter.Seq[E]
Collect(iter.Seq[E]) []E
AppendSeq([]E, iter.Seq[E]) []E
Backward([]E) iter.Seq2[int, E]
Sorted(iter.Seq[E]) []E
SortedFunc(iter.Seq[E], func(E, E) int) []E
SortedStableFunc(iter.Seq[E], func(E, E) int) []E
Repeat([]E, int) []E
Chunk([]E, int) iter.Seq[E]

以下是 maps 包中的新函数。All、Keys 和 Values 返回 map 内容的迭代器。Collect 从迭代器中提取键和值,并返回一个新的 map。

1
2
3
4
5
All(map[K]V) iter.Seq2[K, V]
Keys(map[K]V) iter.Seq[K]
Values(map[K]V) iter.Seq[V]
Collect(iter.Seq2[K, V]) map[K, V]
Insert(map[K, V], iter.Seq2[K, V])

标准库迭代器示例

这里有一个示例,展示了如何使用这些新函数以及我们之前看到的 Filter 函数。这个函数接受一个从 int 到string 的 map,并返回一个只包含 map 中长度至少为某个参数 n 的值的 slice。

1
2
3
4
5
6
7
// LongStrings返回m中长度为n或更长的值的slice。
func LongStrings(m map[int]string, n int) []string {
isLong := func(s string) bool {
return len(s) >= n
}
return slices.Collect(Filter(isLong, maps.Values(m)))
}

maps.Values 函数返回 m 中值的迭代器。Filter 读取该迭代器,并返回一个新的迭代器,其中只包含长字符串。slices.Collect 从该迭代器中读取到一个新的 slice。

当然,你可以很容易地编写一个循环来完成这个任务,而且在许多情况下,循环会更清晰。我们不想鼓励大家一直以这种风格编写代码。也就是说,使用迭代器的优势在于,这类函数可以以相同的方式与任何序列一起工作。在这个例子中,注意 Filter 是如何使用 map 作为输入和 slice 作为输出的,而 Filter 中的代码根本不需要改变。

循环遍历文件中的行

尽管我们看到的大多数示例都涉及到容器,但迭代器是灵活的。

考虑这个简单的代码,它不使用迭代器,来循环遍历字节切片中的行。这是容易编写的,也是相当高效的。

1
2
3
for _, line := range bytes.Split(data, []byte{'\n'}) {
handleLine(line)
}

然而,bytes.Split 确实会分配并返回一个包含行的字节切片。垃圾回收器最终需要做一些工作来释放那个切片。

以下是一个返回某些字节切片中行的迭代器的函数。在通常的迭代器签名之后,函数相当简单。我们不断从 data中提取行,直到没有剩余的,我们将每行传递给 yield 函数。

1
2
3
4
5
6
7
8
9
10
11
12
// Lines返回data中行的迭代器。
func Lines(data []byte) iter.Seq[[]byte] {
return func(yield func([]byte) bool) {
for len(data) > 0 {
line, rest, _ := bytes.Cut(data, []byte{'\n'})
if !yield(line) {
return
}
data = rest
}
}
}

现在我们的代码循环遍历字节切片中的行看起来像这样。

1
2
3
for _, line := range Lines(data) {
handleLine(line)
}

这和之前的代码一样容易编写,而且更有效,因为它不需要分配一个行的切片。

将函数传递给推送迭代器

作为最后一个示例,我们将看到,你不必在范围语句中使用推送迭代器。

之前我们看到了PrintAllElements函数,它打印出集合的每个元素。这里是另一种打印集合所有元素的方法:调用s.All来获取一个迭代器,然后传递一个手写的yield函数。这个yield函数只是打印一个值并返回true。注意这里有两个函数调用:我们调用s.All来获取一个迭代器,它本身是一个函数,我们用我们的手写yield函数调用那个函数。

1
2
3
4
5
6
func PrintAllElements[E comparable](s *Set[E]) {
s.All()(func(v E) bool {
fmt.Println(v)
return true
})
}

没有特别的理由这样写代码。这只是作为一个示例,以展示 yield 函数不是魔法。它可以是你喜欢的任何函数。

更新 go.mod

最后一点注意事项:每个Go模块都指定了它所使用的语言版本。这意味着,要在现有模块中使用新的语言特性,你可能需要更新该版本。这对所有新的语言特性都是适用的;它并不是特定于对函数类型进行范围遍历的功能。由于在Go 1.23版本中新引入了对函数类型进行范围遍历的功能,使用它需要至少指定Go语言版本1.23。

至少有四种方法可以设置语言版本:

  1. 在命令行中运行 go get go@1.23(或者使用 go mod edit -go=1.23 仅编辑go指令)。
  2. 手动编辑go.mod文件并更改go版本行。
  3. 保持模块整体的旧语言版本,但使用 //go:build go1.23 构建标签,以允许在特定文件中使用对函数类型进行范围遍历的功能。

-------------The End-------------

本文标题:[译] Range Over Function Types

文章作者:cloud sjhan

发布时间:2024年08月23日 - 17:08

最后更新:2024年08月23日 - 17:08

原始链接:https://cloudsjhan.github.io/2024/08/23/译-Range-Over-Function-Types/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

cloud sjhan wechat
subscribe to my blog by scanning my public wechat account
坚持原创技术分享,您的支持将鼓励我继续创作!
0%
;