纯与不纯迭代器在Go中的对比
TL;DR
Go现已标准化迭代器。
迭代器功能强大。
迭代器本质上是函数，因此可以是闭包。
文档中提出的迭代器分类存在歧义。
将迭代器分为“纯”和“不纯”两类似乎更合适。
是否应尽可能将迭代器设计为“纯”尚不明确。
Go中迭代器的出现
迭代器模式由经典的“四人帮”书籍推广，定义为：
提供一种顺序访问聚合对象元素的方式，而不暴露其底层表示。
直到最近，可以通过for-range循环迭代的数据结构仅限于数组（直接或通过指针）、切片、字符串、映射、通道和整数。然而，随着Go 1.18对参数多态（又称“泛型”）的支持，Go 1.23标准化了定义自定义迭代器的方式，在标准库中添加了iter包，并在slices和maps包中引入了几个迭代器工厂（即返回迭代器的函数或方法）。Go 1.24标志着标准库中更多迭代器工厂的出现，例如strings.SplitSeq：
1
2
3
4
|
// SplitSeq返回一个迭代器，遍历由sep分隔的s的所有子字符串。
// 迭代器产生的字符串与Split(s, sep)返回的相同，但不构建切片。
// 它返回一个一次性使用的迭代器。
func SplitSeq(s, sep string) iter.Seq[string]
|
如果您不熟悉Go 1.23+中迭代器的语法和语义，我建议您阅读Ian Lance Taylor在Go博客上发表的介绍性文章。一旦您度过了最初的困惑（“为什么这么多函数？！”），一切就会变得顺利。此外，迭代器的调用者通常与其实现中的任何复杂性隔离。
作为第一个例子，考虑下面的程序（playground），其中包含一个名为fib0的工厂函数，该函数生成一个迭代斐波那契数列的迭代器：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
package main
import (
"fmt"
"iter"
)
func fib0() iter.Seq[int] {
return func(yield func(int) bool) {
for a, b := 0, 1; yield(a); a, b = b, a+b {
// 故意为空
}
}
}
func main() {
for n := range fib0() {
if n > 100 {
break
}
fmt.Printf("%d ", n)
}
}
|
正如您所期望的，程序按递增顺序打印小于100的斐波那契数：
1
|
0 1 1 2 3 5 8 13 21 34 55 89
|
迭代器的力量
迭代器的标准化是Go语言的一个受欢迎的增加。迭代器确实提供了切实的好处：
- 它们促进了灵活性和关注点分离：调用者可以不知道序列是如何产生的，而是可以专注于如何处理数据；抽象GitHub API分页消耗的迭代器就是一个很好的例子。
- 它们鼓励封装，因为它们将数据暴露为无法像切片和映射那样突变的序列。
- 它们有潜力提高性能：它们不是物化包含整个数据体的数据结构，而是根据需要逐个分配元素，从而在许多（虽然不是所有）情况下承诺更低的延迟和减少的堆分配；它们也比依赖通道的迭代器实现更高效。
- 它们允许无限序列（例如素数序列），这是像切片和映射这样的有限数据结构永远无法提供的。
因为迭代器如此强大，它们很可能在库中激增，甚至超出Go的标准库。因此，为了防止关于迭代器的讨论中的任何混淆，围绕它们的术语应尽可能精确。
关于迭代器分类的官方指导
“一次性迭代器”这个短语可能在strings.SplitSeq的文档中引起了您的注意。它在iter包的一个部分中解释：
大多数迭代器提供遍历整个序列的能力：当被调用时，迭代器进行任何必要的设置以启动序列，然后在序列的连续元素上调用yield，然后在返回之前进行清理。再次调用迭代器会再次遍历序列。
一些迭代器打破了这一惯例，提供仅能遍历序列一次的能力。这些“一次性迭代器”通常报告来自无法倒带重新开始的数据流的值。在提前停止后再次调用迭代器可能会继续流，但在序列完成后再次调用将不会产生任何值。返回一次性迭代器的函数或方法的文档注释应记录这一事实：
1
2
3
|
// Lines返回一个迭代器，遍历从r读取的行。
// 它返回一个一次性使用的迭代器。
func (r *Reader) Lines() iter.Seq[string]
|
文档的这一段似乎将迭代器分为两类。我将尝试通过几个例子来阐明它们。
“纯”迭代器的例子
我的fib0函数的结果清楚地例示了第一类：
大多数迭代器提供遍历整个序列的能力：当被调用时，迭代器进行任何必要的设置以启动序列，然后在序列的连续元素上调用yield，然后在返回之前进行清理。再次调用迭代器会再次遍历序列。
如果我们将fib0的结果分配给一个变量，然后多次遍历该迭代器，我们确实每次都从头开始遍历斐波那契数列：
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
27
28
29
30
31
32
33
34
35
36
37
38
|
package main
import (
"fmt"
"iter"
)
func fib0() iter.Seq[int] {
return func(yield func(int) bool) {
for a, b := 0, 1; yield(a); a, b = b, a+b {
// 故意为空
}
}
}
func main() {
seq := fib0()
for n := range seq {
if n > 10 {
break
}
fmt.Printf("%d ", n)
}
fmt.Println()
for n := range seq {
if n > 100 {
break
}
fmt.Printf("%d ", n)
}
fmt.Println()
for n := range seq {
if n > 1000 {
break
}
fmt.Printf("%d ", n)
}
}
|
输出：
1
2
3
|
0 1 1 2 3 5 8
0 1 1 2 3 5 8 13 21 34 55 89
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
|
根据我对文档的解释，第一类迭代器对应于外部纯函数，即迭代器可能在内部依赖突变，但显示没有外部可观察的副作用。因此，“纯”似乎是我对这类迭代器的合适限定词；“无状态”是次选。
“一次性”迭代器的例子
第二类呢？
一些迭代器打破了这一惯例，提供仅能遍历序列一次的能力。这些“一次性迭代器”通常报告来自无法倒带重新开始的数据流的值。在提前停止后再次调用迭代器可能会继续流，但在序列完成后再次调用将不会产生任何值。
考虑下面的例子：
1
2
3
4
5
6
7
8
|
func fib1() iter.Seq[int] {
a, b := 0, 1
return func(yield func(int) bool) {
for ; yield(a); a, b = b, a+b {
// 故意为空体
}
}
}
|
乍一看，迭代器工厂fib1似乎几乎与fib0相同，您可能会原谅它们实现上的差异不重要；事实上，如果您这样认为，您会很有伴。然而，fib1和fib0之间的差异远非仅仅是表面上的，实际上改变了它们结果的语义。要理解为什么，您需要对闭包有些熟悉。
如有必要，请参考本文的附录以复习闭包。
回想一下，在Go中，迭代器是函数；因此，迭代器可以是闭包！在fib0中，变量a和b在结果迭代器内部声明。相反，在fib1中，变量a和b是结果迭代器的自由变量，该迭代器也恰好突变这些变量。因此，如果我们像之前对fib0的结果那样重复遍历fib1的结果（playground），我们会观察到非常不同的行为：
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
27
28
29
30
31
32
33
34
35
36
37
38
39
|
package main
import (
"fmt"
"iter"
)
func fib1() iter.Seq[int] {
a, b := 0, 1
return func(yield func(int) bool) {
for ; yield(a); a, b = b, a+b {
// 故意为空
}
}
}
func main() {
seq := fib1()
for n := range seq {
if n > 10 {
break
}
fmt.Printf("%d ", n)
}
fmt.Println()
for n := range seq {
if n > 100 {
break
}
fmt.Printf("%d ", n)
}
fmt.Println()
for n := range seq {
if n > 1000 {
break
}
fmt.Printf("%d ", n)
}
}
|
输出：
1
2
3
|
0 1 1 2 3 5 8
13 21 34 55 89
144 233 377 610 987
|
简单来说，迭代器“记住”调用者上次在斐波那契数列中停止的位置，当调用者恢复遍历时，迭代器从它离开的地方继续；因为这个迭代器产生的序列无法倒带但可以恢复，所以迭代器可能被描述为“一次性”但“可恢复”。
有问题的分类
在我看来，文档中建议的迭代器分类并不理想。
首先，它缺乏一个术语来描述我 earlier 描述的“纯”迭代器，这令人困惑。在所有迭代器中，“纯”迭代器 arguably 作为最容易推理的迭代器而脱颖而出；因此，它们不应该有自己的限定词吗？与动力系统的类比浮现在脑海中：线性动力系统从非线性系统中 singled out， precisely 因为它们被认为更简单且更容易理解。
其次，我发现第二类的描述令人困惑地不精确和模糊。特别是，“一次性”这个术语是否旨在仅涵盖某些还是所有“不纯”迭代器，这对我来说不清楚……如果我相信我最近在Gophers Slack上进行的一次非正式投票的结果，对其他Gophers来说也不清楚。如果“一次性”限定词仅用于“不纯”迭代器的一个子类别，我不确定为什么这个子类别应该在文档中受到特别关注。如果“一次性”限定词旨在用于所有“不纯”迭代器，那么它 strike 我作为一个误称；毕竟，许多形式的“不纯”迭代器是可能的，并非所有都可以合理地描述为“一次性”，正如我们将看到的。
“不纯”迭代器的奇妙动物园
在下面的程序中，fib2产生的迭代器（playground）可以合理地描述为“可使用两次”和“不可恢复”（或者，也许，重新启动）：
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
package main
import (
"fmt"
"iter"
)
func fib2() iter.Seq[int] {
var n int
return func(yield func(n int) bool) {
if n > 1 {
return
}
for a, b := 0, 1; yield(a); a, b = b, a+b {
// 故意为空体
}
n++
}
}
func main() {
seq := fib2()
for n := range seq {
if n > 10 {
break
}
fmt.Printf("%d ", n)
}
fmt.Println()
for n := range seq {
if n > 100 {
break
}
fmt.Printf("%d ", n)
}
fmt.Println()
for n := range seq {
if n > 1000 {
break
}
fmt.Printf("%d ", n)
}
}
|
输出：
1
2
|
0 1 1 2 3 5 8
0 1 1 2 3 5 8 13 21 34 55 89
|
在下面的程序中，fib3产生的迭代器（playground）可以合理地描述为“可使用两次”和“可恢复”：
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
package main
import (
"fmt"
"iter"
)
func fib3() iter.Seq[int] {
var n int
a, b := 0, 1
return func(yield func(n int) bool) {
if n > 1 {
return
}
for ; yield(a); a, b = b, a+b {
// 故意为空体
}
n++
}
}
func main() {
seq := fib3()
for n := range seq {
if n > 10 {
break
}
fmt.Printf("%d ", n)
}
fmt.Println()
for n := range seq {
if n > 100 {
break
}
fmt.Printf("%d ", n)
}
fmt.Println()
for n := range seq {
if n > 1000 {
break
}
fmt.Printf("%d ", n)
}
}
|
输出：
1
2
|
0 1 1 2 3 5 8
13 21 34 55 89
|
我相信您可以想到更多围绕这个主题的变体。一旦函数纯度消失，可能性是无限的。
是否应尽可能将迭代器设计为“纯”？
另一个问题出现了：如果“纯”迭代器比“不纯”迭代器更容易推理，那么迭代器不应该尽可能设计为“纯”吗？
性能考虑
也许它们应该，至少当我们强调性能作为设计标准时。“纯”迭代器确实往往比它们的“不纯”对应物产生更少的堆分配。以strings.Lines作为案例研究；下面显示的是它在Go 1.24.3中的源代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
// Lines返回一个迭代器，遍历字符串s中以换行符终止的行。
// 迭代器产生的行包括它们的终止换行符。
// 如果s为空，迭代器不产生任何行。
// 如果s不以换行符结束，最后产生的行将不以换行符结束。
// 它返回一个一次性使用的迭代器。
func Lines(s string) iter.Seq[string] {
return func(yield func(string) bool) {
for len(s) > 0 {
var line string
if i := IndexByte(s, '\n'); i >= 0 {
line, s = s[:i+1], s[i+1:]
} else {
line, s = s, ""
}
if !yield(line) {
return
}
}
return
}
}
|
结果迭代器是“不纯”的，因为它突变s，这恰好是它唯一的自由变量。作为逃逸分析的结果，s逃逸到堆：
1
2
3
4
|
$ go build -gcflags='-m=2' ./strings
-snip-
strings/iter.go:18:12: s escapes to heap:
-snip-
|
但strings.Lines本可以设计为产生一个“纯”迭代器：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
func Lines(s string) iter.Seq[string] {
return func(yield func(string) bool) {
s := s // 本地副本！
for len(s) > 0 {
var line string
if i := strings.IndexByte(s, '\n'); i >= 0 {
line, s = s[:i+1], s[i+1:]
} else {
line, s = s, ""
}
if !yield(line) {
return
}
}
return
}
}
|
在这个strings.Lines的替代版本中，它的s参数仍然是结果迭代器的自由变量，但迭代器不突变该变量；相反，迭代器专门操作源字符串的本地副本。通过这个简单的更改，逃逸分析不再得出结论变量s需要逃逸到堆，并且需要少一次内存分配。参见Alan Donovan在GitHub上的相关评论。
与相关迭代器的一致性
然而，性能只是可能的设计标准之一：正如Ian Lance Taylor精明地向我指出的，与紧密链接的迭代器工厂的行为一致性是另一个。例如，包bytes提供了一个名为Lines的函数，类似于strings.Lines；下面显示的是它在Go 1.24.3中的源代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
// Lines返回一个迭代器，遍历字节切片s中以换行符终止的行。
// 迭代器产生的行包括它们的终止换行符。
// 如果s为空，迭代器不产生任何行。
// 如果s不以换行符结束，最后产生的行将不以换行符结束。
// 它返回一个一次性使用的迭代器。
func Lines(s []byte) iter.Seq[[]byte] {
return func(yield func([]byte) bool) {
for len(s) > 0 {
var line []byte
if i := IndexByte(s, '\n'); i >= 0 {
line, s = s[:i+1], s[i+1:]
} else {
line, s = s, nil
}
if !yield(line[:len(line):len(line)]) {
return
}
}
return
}
}
|
尽管我想重新设计bytes.Lines以使其产品“纯”，但我想不出一种高效的方法。与字符串相反，切片是可变的；此外，多个切片可以引用同一个底层数组。因此，即使结果迭代器被修改为操作源切片的本地副本，它仍然不会是“纯”的，如下面程序所示（playground）：
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
package main
import (
"bytes"
"fmt"
"iter"
"os"
)
func main() {
src := []byte("foo\nbar\nbaz\n")
seq := Lines(src)
for s := range seq {
os.Stdout.Write(s)
}
for s := range seq { // 传递突变源切片的通道
if len(s) == 0 {
continue
}
s[0] = 'a'
}
fmt.Println()
for s := range seq {
os.Stdout.Write(s)
}
}
func Lines(s []byte) iter.Seq[[]byte] {
return func(yield func([]byte) bool) {
s := s // 本地副本
for len(s) > 0 {
var line []byte
if i := bytes.IndexByte(s, '\n'); i >= 0 {
line, s = s[:i+1], s[i+1:]
} else {
line, s = s, nil
}
if !yield(line[:len(line):len(line)]) {
return
}
}
return
}
}
|