反向而行

# Going Backward Source: https://antonz.org/going-backward/ Go 标准库中的 `slices` 包有一个名为 `Backward` 的函数。它允许你按相反顺序遍历切片中的元素： ``` // Backward returns an iterator over index-value pairs in the slice, // traversing it backward with descending indices. func Backward[Slice ~[]E, E any](s Slice) iter.Seq2[int, E] ``` 如果你对泛型和迭代器不太熟悉，看到这个签名（以及 `slices` 包中的其他签名）时，自然会想：“难道不能把它弄得更简单一点吗？” 为了回答这个问题，让我们做一个思想实验。想象自己是生活在迭代器时代之前的遥远祖先，决定从头实现 `Backward`。 > 我们想象中的祖先不在 Google 工作，所以不要把他们的决定投射到 Go 开发团队身上。他们有自己理由——而且没有 Jira。 ## 1. 反转切片 一个宜人、阳光明媚的夏日，鸟儿在歌唱。你像往常一样坐在键盘前，突然决定写一个函数来反向遍历切片。做什么都比继续处理又一个 Jira 工单强。 ``` // Backward returns the slice in reverse order. func Backward[T any](s []T) []T { n := len(s) res := make([]T, n) for i := n - 1; i >= 0; i-- { res[n-1-i] = s[i] } return res } ``` 使用示例： ``` s := []int{11, 22, 33, 44, 55} b := Backward(s) fmt.Println(b) // [55 44 33 22 11] ``` 这个实现简单且可靠。不过有一个缺点：`Backward` 创建了切片的一个副本，对于大型切片来说可能很浪费。 此外，太阳躲到了云后，看起来要下雨了。你决定再多做一点工作。 ## 2. 给我，给我，给我 为了避免复制切片，你决定返回一个闭包，它知道原切片中的当前位置，并在每次调用时返回下一个元素： ``` // Backward returns a function that, on each call, returns the next // element of the slice (in reverse order) and a flag indicating // whether to continue iterating (false means done). func Backward[T any](s []T) func() (T, bool) { i := len(s) return func() (T, bool) { if i == 0 { var zero T return zero, false } i-- return s[i], true } } ``` 使用示例： ``` s := []int{11, 22, 33, 44, 55} next := Backward(s) for { v, ok := next() if !ok { break } fmt.Print(v, " ") } fmt.Println() // 55 44 33 22 11 ``` 现在它只分配 O(1) 的内存，而不是 O(n)。这样更好。 在继续之前，你瞥了一眼窗外。是的，果然下雨了，天空比之前更加阴沉。真是适合工作的好天气！ ## 3. 基于回调的迭代器 调用代码中有些东西一直困扰着你。它显得相当命令式。你希望把循环机制交给 `Backward`，让调用者只负责应用逻辑（无论你对切片元素做什么）。 你决定让 `Backward` 的签名稍微复杂一点。现在它将返回一个迭代器函数，该函数接受一个回调作为参数，并将其应用于切片的每个元素： ``` // Backward returns a function that takes a yield callback. // The callback is invoked for each element of the slice (in reverse order). func Backward[T any](s []T) func(yield func(T) bool) { return func(yield func(T) bool) { for i := len(s) - 1; i >= 0; i-- { if !yield(s[i]) { return } } } } ``` `yield` 函数返回 `bool`——这样回调就可以在希望提前停止遍历时发出信号。 现在你可以把调用代码中的 `for` 循环体转换成一个回调，不再需要循环了： ``` work := func(x int) bool { if x < 30 { return false // early exit } fmt.Print(x, " ") return true } s := []int{11, 22, 33, 44, 55} it := Backward(s) it(work) fmt.Println() // 55 44 33 ``` 嗯，很有函数式风格。 一个小细节：`Backward` 的签名看起来有点重。你为返回值添加了一个单独的类型： ``` // Seq is an iterator over sequences of individual values. // When called as seq(yield), seq calls yield(v) for each value // v in the sequence, stopping early if yield returns false. type Seq[T any] func(yield func(T) bool) ``` 这个函数现在看起来好多了： ``` func Backward[T any](s []T) Seq[T] { // body unchanged } ``` 你一边称赞自己发明了迭代器，一边走到窗边。看起来天气变得更糟了。大雨倾盆而下，天空阴云密布，暗得像傍晚一样。 ## 4. 迭代器 2：迭代器的回归 一切都很棒，但随后你意识到：普通的 `range` 遍历切片会同时返回索引和元素值。而你的迭代器只返回值。你决定修复这个令人烦恼的疏忽： ``` func Backward[T any](s []T) func(yield func(int, T) bool) { return func(yield func(int, T) bool) { for i := len(s) - 1; i >= 0; i-- { if !yield(i, s[i]) { return } } } } ``` 使用示例： ``` work := func(i int, x int) bool { fmt.Print(i, ":", x, " ") return true } s := []int{11, 22, 33, 44, 55} it := Backward(s) it(work) fmt.Println() // 4:55 3:44 2:33 1:22 0:11 ``` 由于结果的签名已经改变，它不再适合 `Seq` 类型。你能怎么办呢——只能添加一个新类型。经过十分钟的深思熟虑，你决定把它叫做 `Seq2`： ``` // Seq2 is an iterator over sequences of key-value pairs. // When called as seq(yield), seq calls yield(k, v) for each pair // (k, v) in the sequence, stopping early if yield returns false. type Seq2[K any, V any] func(yield func(K, V) bool) ``` ``` func Backward[T any](s []T) Seq2[int, T] { // body unchanged } ``` 你站起来伸了伸腿，走到窗边。暴雨大到什么都看不清。闪电划过。拳头大小的冰雹落下——你这辈子从未见过这样的景象。好吧，这种情况时有发生！ ## 5. 不完全是切片 你想到了所有事情吗？似乎是这样。但你还不打算回到 Jira 工单。回顾 Go 规范，你意识到除了普通切片之外，还有“用户自定义”的切片——底层类型是切片的类型： ``` // IDs is a slice of identifiers. type IDs []int ``` `Backward` 对 `IDs` 也能很好地工作——编译器接受 `IDs` 类型的值，因为其底层类型是 `[]int`： ``` ids := IDs{11, 22, 33, 44, 55} it := Backward(ids) it(work) fmt.Println() // 4:55 3:44 2:33 1:22 0:11 ``` 但下面这种情况呢？ ``` // backwardIDs builds an iterator over a slice of identifiers // in reverse order. var backwardIDs func(IDs) Seq2[int, int] = Backward[int] // ERROR: cannot use Backward[int] // (value of type func(s []int) Seq2[int, int]) // as func(IDs) Seq2[int, int] value in variable declaration ``` 这就是 `IDs` 和 `[]int` 之间的差异体现出来的地方。 当你赋值函数本身时，比较的是签名：`func(IDs) Seq2[int, int]` 与 `func([]int) Seq2[int, int]`。只有参数类型相同，签名才匹配。但 `IDs` 和 `[]int` 是不同的，即使一个基于另一个。签名不同 → 你会收到错误。 你挠了挠头，再次查看规范，发现了一种特殊的泛型语法：`~T`。它表示所有底层类型为 `T` 的类型的集合。正是你所需要的！ 现在你不仅要参数化元素类型（`E`），还要参数化切片类型（`Slice`）。`E` 用于返回值，而 `Slice` 使函数不仅接受 `[]E`，还接受基于它的任何类型： ``` func Backward[Slice ~[]E, E any](s Slice) Seq2[int, E] { return func(yield func(int, E) bool) { for i := len(s) - 1; i >= 0; i-- { if !yield(i, s[i]) { return } } } } ``` 现在示例： ``` var backwardIDs func(IDs) Seq2[int, int] = Backward[IDs, int] ids := IDs{11, 22, 33, 44, 55} work := func(i int, x int) bool { fmt.Print(i, ":", x, " ") return true } it := backwardIDs(ids) it(work) fmt.Println() // 4:55 3:44 2:33 1:22 0:11 ``` 它工作了！你最终得到了类似于 `slices` 包中 `Backward` 的东西。 你疲惫地呼了口气，走到窗边。暴雨和冰雹已经让位于飓风。树木和广告牌飞过。不知为何，蟾蜍正从天而降。 ## 6. 迭代器 3：审判日 为了不去想窗外发生的怪事，你继续思考。 普通的 `Backward` 已经很棒了。但如果遍历逻辑本身可配置，那就更好了。另一方面，如果最终参数太多，策略模式会更合适。而且，顺便说一下，添加一个根据给定条件生成迭代器工厂的工厂也无妨…… 你还没想完，窗外的地面就传来震耳欲聋的轰鸣声裂开了。一只巨大的黑手，流淌着熔岩，闪烁着火焰，从裂口中伸出，抓住你，径直把你拖入地狱。 > P.S. 尽管本文带有调侃的意味，但标准库中“复杂”的版本是合理的（https://go.dev/blog/deconstructing-type-parameters）（`Backward` 只是与包中的其他函数保持一致）。但如果你在一个解决特定问题的项目中做类似的事情——停在更简单的选项上可能是合理的。 ★ 订阅 (https://antonz.org/subscribe/) 以获取新文章更新。