简介

这是我在2024年GopherCon大会上演讲的博客文章版本。

函数类型的range是Go 1.23版本中的一个新语言特性。这篇博文将解释为什么我们要添加这个新特性,它究竟是什么,以及如何使用它。

为什么?

自Go 1.18以来,我们已经能够在Go中编写新的泛型容器类型。例如,让我们考虑这个非常简单的Set类型,一个基于map实现的泛型类型。

type Set[E comparable] struct {
    m map[E]struct{}
}

自然,set类型有一种添加元素的方法和一种检查元素是否存在的方法。这里的细节并不重要。

func (s *Set[E]) Add(v E) {
    s.m[v] = struct{}{}
}

func (s *Set[E]) Contains(v E) bool {
    _, ok := s.m[v]
    return ok
}

除此之外,我们还需要一个函数来返回两个集合的并集。

func Union[E comparable](s1, s2 *Set[E]) *Set[E] {
    r := &Set[E]{m: make(map[E]struct{})}
    for v := range s1.m {
        r.m[v] = struct{}{}
    }
    for v := range s2.m {
        r.m[v] = struct{}{}
    }
    return r
}

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

但是有很多原因可能导致某人想要遍历set中的所有元素。这个set包必须为其用户提供某种方式来做到这一点。

这应该如何工作呢?

推送Set元素

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

func (s *Set[E]) Push(yield func(E) bool) {
    for v := range s.m {
        if !yield(v) {
            break
        }
    }
}

在Go标准库中,我们看到这种通用模式被用于 sync.Map.Range^[2] 方法、 flag.Visit^[3] 函数和 filepath.Walk^[4] 函数等情况。这是一种通用模式,而不是完全相同的模式;事实上,这三个例子的工作方式都不完全相同。

这就是使用Push方法打印set中所有元素的样子:你用一个对元素进行所需操作的函数调用Push。

s.Push(func(v string) bool {
    fmt.Println(v)
    return true
})

拉取Set元素

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

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

func (s *Set[E]) Pull() (next func() (E, bool), stop func()) {
    ch := make(chan E)
    done := make(chan struct{})
    go func() {
        defer close(ch)
        for v := range s.m {
            select {
            case ch <- v:
            case <-done:
                return
            }
        }
    }()
    return func() (E, bool) {
            v, ok := <-ch
            return v, ok
        },
        func() {
            close(done)
            // Drain channel to let the goroutine exit.
            for range ch {
            }
        }
}

标准库中没有完全以这种方式工作的内容。 runtime.CallersFrames^[5] 和 reflect.Value.MapRange^[6] 都类似,尽管它们返回带有方法的值,而不是直接返回函数。

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

next, stop := s.Pull()
defer stop()
for {
    v, ok := next()
    if !ok {
        break
    }
    fmt.Println(v)
}

标准化方法

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

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

迭代器

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

1994年首次出版的流行 设计模式书^[7] 将其描述为迭代器模式。你使用迭代器来"提供一种方法,以顺序访问聚合对象的元素,而不暴露其底层表示"。这个引用中所说的聚合对象就是我一直称之为容器的东西。聚合对象,或容器,只是一个包含其他值的值,就像我们一直在讨论的Set类型。

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

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

然而,1.23版本之前的Go并没有提供迭代器。

For/range

众所周知,Go有内置于语言中的容器类型:切片、数组和映射。它还有一种访问这些值的元素而不暴露底层表示的方法:for/range语句。for/range语句适用于Go的内置容器类型(也适用于字符串、通道,从Go 1.22开始还适用于int)。

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

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

本次发布的改进

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

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

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

对(某些)函数类型进行Range

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

func(yield func(T) bool)
func(yield func(T) bool) bool
func(yield func(T1, T2) bool)
func(yield func(T1, T2) bool) bool

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

标准(推送)迭代器

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

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

Seq和Seq2的区别仅在于Seq2是一对值的序列,例如来自映射的键和值。在这篇文章中,为了简单起见,我们将重点关注Seq,但我们所说的大部分内容也适用于Seq2。

用一个例子来解释迭代器如何工作最容易。这里Set方法All返回一个函数。All的返回类型是iter.Seq[E],所以我们知道它返回一个迭代器。

func (s *Set[E]) All() iter.Seq[E] {
    return func(yield func(E) bool) {
        for v := range s.m {
            if !yield(v) {
                return
            }
        }
    }
}

迭代器函数本身接受另一个函数作为参数,即yield函数。迭代器用set中的每个值调用yield函数。在这种情况下,迭代器(由Set.All返回的函数)很像我们之前看到的Set.Push函数。

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

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

首先是,一旦你越过这个函数代码的第一行,迭代器的实际实现非常简单:用set的每个元素调用yield,如果yield返回false就停止。

for v := range s.m {
    if !yield(v) {
        return
    }
}

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

for v := range s.All() {
    fmt.Println(v)
}

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

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

拉取迭代器

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

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

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

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

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

你可以自己编写一个拉取迭代器,但通常你不必这样做。新的标准库函数 iter.Pull^[9] 接受一个标准迭代器,也就是说一个推送迭代器函数,并返回一对函数。第一个是拉取迭代器:一个函数,每次调用时都返回序列中的下一个值。第二个是stop函数,应在我们完成拉取迭代器时调用。这类似于我们之前看到的Set.Pull方法。

iter.Pull返回的第一个函数,即拉取迭代器,返回一个值和一个报告该值是否有效的布尔值。在序列结束时,布尔值将为false。

iter.Pull返回一个stop函数,以防我们没有读完整个序列。在一般情况下,推送迭代器(即iter.Pull的参数)可能会启动goroutine,或构建需要在迭代完成时清理的新数据结构。当yield函数返回false时,表示不再需要更多值,推送迭代器将进行任何清理。当与for/range语句一起使用时,for/range语句将确保如果循环提前退出(通过break语句或任何其他原因),则yield函数将返回false。另一方面,对于拉取迭代器,没有办法强制yield函数返回false,所以需要stop函数。

另一种说法是,调用stop函数会导致push迭代器调用yield函数时返回false。

严格来说,如果pull迭代器返回false表示已到达序列末尾,就不需要调用stop函数,但通常更简单的做法是总是调用它。

下面是一个使用pull迭代器并行遍历两个序列的例子。这个函数报告两个任意序列是否包含相同顺序的相同元素。

// EqSeq reports whether two iterators contain the same
// elements in the same order.
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将两个push迭代器s1和s2转换为pull迭代器。它使用defer语句确保在使用完毕后停止pull迭代器。

然后代码循环调用pull迭代器来检索值。如果第一个序列结束,则在第二个序列也结束时返回true,否则返回false。如果值不同,则返回false。然后循环拉取下两个值。

与push迭代器一样,Go运行时中有一些复杂性来使pull迭代器高效,但这不会影响实际使用iter.Pull函数的代码。

迭代迭代器

现在你已经了解了关于函数类型的range和迭代器的所有知识。我们希望你喜欢使用它们!

不过,还有一些值得一提的事情。

适配器

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

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

// Filter returns a sequence that contains the elements
// of s for which f returns 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
                }
            }
        }
    }
}

与前面的例子一样,当你第一次看到函数签名时,它们看起来很复杂。一旦你理解了签名,实现就很简单了。

        for v := range s {
            if f(v) {
                if !yield(v) {
                    return
                }
            }
        }

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

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

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

二叉树

作为push迭代器在遍历容器类型时多么方便的一个例子,让我们考虑这个简单的二叉树类型。

// Tree is a binary tree.
type Tree[E any] struct {
    val         E
    left, right *Tree[E]
}

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

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

// All returns an iterator over the values in t.
func (t *Tree[E]) All() iter.Seq[E] {
    return func(yield func(E) bool) {
        t.push(yield)
    }
}

// push pushes all elements to the yield function.
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是返回切片元素迭代器的函数。Collect从迭代器中获取值并返回包含这些值的切片。其他函数请参阅文档。

• All([]E) iter.Seq2[int, E]^[10]
• Values([]E) iter.Seq[E]^[11]
• Collect(iter.Seq[E]) []E^[12]
• AppendSeq([]E, iter.Seq[E]) []E^[13]
• Backward([]E) iter.Seq2[int, E]^[14]
• Sorted(iter.Seq[E]) []E^[15]
• SortedFunc(iter.Seq[E], func(E, E) int) []E^[16]
• SortedStableFunc(iter.Seq[E], func(E, E) int) []E^[17]
• Repeat([]E, int) []E^[18]
• Chunk([]E, int) iter.Seq([]E)^[19]

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

• All(map[K]V) iter.Seq2[K, V]^[20]
• Keys(map[K]V) iter.Seq[K]^[21]
• Values(map[K]V) iter.Seq[V]^[22]
• Collect(iter.Seq2[K, V]) map[K, V]^[23]
• Insert(map[K, V], iter.Seq2[K, V])^[24]

标准库迭代器示例

这里是一个如何使用这些新函数以及我们之前看到的Filter函数的例子。这个函数接受一个从int到string的map,并返回一个只包含map中长度大于某个参数n的值的切片。

// LongStrings returns a slice of just the values
// in m whose length is n or more.
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从该迭代器读取到一个新的切片中。

当然,你可以很容易地写一个循环来做这件事,在许多情况下循环会更清晰。我们不想鼓励每个人总是以这种风格编写代码。话虽如此,使用迭代器的优点是这种函数对任何序列都以相同的方式工作。在这个例子中,注意Filter如何使用map作为输入和切片作为输出,而完全不需要更改Filter中的代码。

遍历文件中的行

虽然我们看到的大多数例子都涉及容器,但迭代器是灵活的。

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

    nl := []byte{'\n'}
    // Trim a trailing newline to avoid a final empty blank line.
    for _, line := range bytes.Split(bytes.TrimSuffix(data, nl), nl) {
        handleLine(line)
    }

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

这里有一个函数,它返回某个字节切片中行的迭代器。在常见的迭代器签名之后,函数非常简单。我们不断从数据中提取行,直到没有剩余,并将每一行传递给yield函数。

// Lines returns an iterator over lines in 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
        }
    }
}

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

    for line := range Lines(data) {
        handleLine(line)
    }

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

将函数传递给push迭代器

对于我们的最后一个例子,我们将看到你不必在range语句中使用push迭代器。

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

func PrintAllElements[E comparable](s *Set[E]) {
    s.All()(func(v E) bool {
        fmt.Println(v)
        return true
    })
}

没有特别的理由要这样编写这段代码。这只是一个例子,展示yield函数并不神奇。它可以是你喜欢的任何函数。

更新go.mod

最后一点说明:每个Go模块都指定了它使用的语言版本。这意味着为了在现有模块中使用新的语言特性,你可能需要更新该版本。这对所有新的语言特性都是如此;这不是函数类型range特有的。由于函数类型range是Go 1.23版本中的新特性,使用它需要至少指定Go语言版本1.23。

设置语言版本有(至少)四种方法:

• 在命令行上运行go get go@1.23(或go mod edit -go=1.23只编辑go指令)。
• 手动编辑go.mod文件并更改go行。
• 保持模块整体的旧语言版本,但使用//go:build go1.23构建标记允许在特定文件中使用函数类型range。

参考链接

1. Go博客: https://go.dev/blog/
2. sync.Map.Range: https://pkg.go.dev/sync#Map.Range
3. flag.Visit: https://pkg.go.dev/flag#Visit
4. filepath.Walk: https://pkg.go.dev/path/filepath#Walk
5. runtime.CallersFrames: https://pkg.go.dev/runtime#CallersFrames
6. reflect.Value.MapRange: https://pkg.go.dev/reflect#Value.MapRange
7. 设计模式书: https://en.wikipedia.org/wiki/Design_Patterns
8. CLU语言: https://en.wikipedia.org/wiki/CLU_(programming_language)
9. iter.Pull: https://pkg.go.dev/iter#Pull
10. All([]E) iter.Seq2[int, E]: https://pkg.go.dev/slices#All
11. Values([]E) iter.Seq[E]: https://pkg.go.dev/slices#Values
12. Collect(iter.Seq[E]) []E: https://pkg.go.dev/slices#Collect
13. AppendSeq([]E, iter.Seq[E]) []E: https://pkg.go.dev/slices#AppendSeq
14. Backward([]E) iter.Seq2[int, E]: https://pkg.go.dev/slices#Backward
15. Sorted(iter.Seq[E]) []E: https://pkg.go.dev/slices#Sorted
16. SortedFunc(iter.Seq[E], func(E, E) int) []E: https://pkg.go.dev/slices#SortedFunc
17. SortedStableFunc(iter.Seq[E], func(E, E) int) []E: https://pkg.go.dev/slices#SortedStableFunc
18. Repeat([]E, int) []E: https://pkg.go.dev/slices#Repeat
19. Chunk([]E, int) iter.Seq([]E): https://pkg.go.dev/slices#Chunk
20. All(map[K]V) iter.Seq2[K, V]: https://pkg.go.dev/maps#All
21. Keys(map[K]V) iter.Seq[K]: https://pkg.go.dev/maps#Keys
22. Values(map[K]V) iter.Seq[V]: https://pkg.go.dev/maps#Values
23. Collect(iter.Seq2[K, V]) map[K, V]: https://pkg.go.dev/maps#Collect
24. Insert(map[K, V], iter.Seq2[K, V]): https://pkg.go.dev/maps#Insert