[译] Range Over Function Types

发表于 | 分类于 | 阅读次数: |
| 字数统计: 6,346 | 阅读时长 ≈ 25

在 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.CallersFrames 和 reflect.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%
;