第 13 章 · 迭代与惰性：迭代器协议、生成器、推导式与 LINQ

解决什么问题：一串数据太长、算起来太贵，甚至根本没有尽头时，怎样一个一个地取，用到哪里算到哪里。

四种语言的态度：Python、JS/TS、C# 都是调用方拉取的迭代器，再用 yield 生成器把普通循环变成迭代器；Go 没有生成器，1.23 起用接收 yield 回调的函数做推送式迭代器。

一个场景

从一个无穷的计数器（0、1、2……）里挑出偶数，算出平方，只要前 5 个。计数器没有尽头，所以不能先把“全部自然数”造成一个列表再过滤，那样程序永远停不下来。为了证明整条流水线是惰性的，计数器每产出一个数就记一笔：取到第 5 个偶数 8 时一切停下，源头一共只产出了 0 到 8 这九个数。四种语言都打印同样的两行。

概念本身

for 循环最初只是“下标从 0 走到长度减 1”。可是要遍历的东西常常不是数组：文件里的行、分页返回的接口数据、树的节点，有的太大放不进内存，有的要一边读一边产生，有的根本没有尽头。语言需要一种统一的说法，让任何“能一个一个给出元素”的东西都能放进 for，这就是迭代器协议（iterator protocol）。它只有两句话：“给我下一个”和“已经没有了”。能回答这两句话的对象叫迭代器（iterator），它自己记着走到了哪里；能造出迭代器的对象叫可迭代对象（iterable），列表就是，每次 for 都向它要一个新的迭代器，从头开始。

由谁来推动，分出两种风格。拉取式（pull）由消费者调用 next，要一个给一个，节奏在消费者手里；迭代器是个被动的对象，两次调用之间得自己记住进度。推送式（push）反过来，迭代器是一个带循环的普通函数，每算出一个值就调用消费者交给它的回调，消费者只能通过回调的返回值说“够了”。拉取式用起来灵活，两个序列可以交替着取，随时可以停；可手写起来麻烦，循环得拆成显式的状态。推送式写起来就是一个循环，可消费者失去了主动权。

拉取式与推送式的控制流

看两栏里谁调用谁：左栏的实线从消费者出发，生成器每次被叫醒才往前走一步；右栏里真正干活的箭头从 squares 指向循环体，循环体反倒成了被调用的一方，只能靠虚线上的 true 或 false 回话。

生成器（generator）把两者的长处接到一起：写的时候是一个普通循环，遇到 yield 就把值交出去并暂停，下次有人要值时从暂停处接着跑，局部变量原样还在。对调用方来说，它就是一个拉取式迭代器。换句话说，生成器是一个可以暂停和恢复的函数，进度不再需要手工保存，函数停在哪一行本身就是进度。

最后是惰性求值（lazy evaluation）和急切求值（eager evaluation）。急切的写法每一步都先把整批结果算完再交给下一步：“先过滤出所有偶数，再全部平方，再取前 5 个”，源头无穷时第一步就停不下来。惰性的写法里每一步都只是一个包着上游的迭代器，搭好时什么也不算；消费者要一个值，请求才往上游传一格。

惰性流水线里请求和值的流动

看 filter 那一格：它收到一次请求，遇到奇数就丢掉、自己再向 counter 要一个，所以消费者拿到 5 个值，counter 被要了 9 次；take 满 5 个之后不再往上要，流水线到此为止。

Python 怎么做

Python 的迭代是原生的：可迭代对象有 __iter__ 方法返回迭代器，迭代器的 __next__ 返回下一个值，没有了就抛出 StopIteration。for 循环、list()、解包、sum() 都走这套协议。生成器函数从 2.2 起就有（PEP 255），生成器表达式从 2.4 起有（PEP 289）；Python 3 又把 range、map、filter、zip 都改成了惰性的。

from itertools import count, islice

pulled = 0  # 源头一共产出了几个数


def counter():
    global pulled
    for n in count():  # 0、1、2……永不结束
        pulled += 1
        yield n  # 交出 n，函数在这里暂停，下次 next() 从这里继续


evens = (n for n in counter() if n % 2 == 0)  # 圆括号：生成器表达式，此刻什么都没算
squares = (n * n for n in evens)
first5 = list(islice(squares, 5))  # list() 一次次调用 next()，拿够 5 个就停

print("前 5 个偶数的平方：" + " ".join(str(n) for n in first5))
print(f"实际从源头取了：{pulled} 个数")

# 输出：
# 前 5 个偶数的平方：0 4 16 36 64
# 实际从源头取了：9 个数

运行：python lazy.py。函数体里出现 yield，counter() 就不再执行函数体，而是返回一个生成器对象。itertools.count() 本身已经是无穷迭代器，这里再包一层生成器只是为了记数。两个圆括号的生成器表达式各包住上游，islice 是迭代器版的切片：迭代器不支持 squares[:5] 这样的下标，因为它根本不知道后面还有多少。

for x in obj 相当于先 it = iter(obj)，再反复 next(it)，接到 StopIteration 就结束循环。不用生成器也能写迭代器：一个类的 __iter__ 返回自己，__next__ 用实例属性记住下一个数，每次加一后返回。生成器把这个类连同进度字段一起替你造好。islice 交出第 5 个值后，第 6 次被调用时先看计数已满，直接报告结束，不再向上游要，所以 pulled 停在 9。

底层怎么实现。 调用生成器函数时，CPython 创建一个生成器对象，里面保存着这个函数的帧（frame）：局部变量、求值栈、执行到哪条字节码；3.11 起这一帧直接嵌在生成器对象里。next() 把这一帧接到当前调用栈上，从记下的位置继续解释执行；执行到 yield 时，值交给调用方，帧从调用栈上摘下，但完整地留在生成器对象里。挂起的只是生成器自己这一帧：它调用的函数里不能替它 yield，要把另一个生成器的值转交出去得写 yield from。函数体执行完，next() 就抛出 StopIteration。

同一套机制后来被扩展：send() 能把值送回暂停处（PEP 342），yield from 能委托给子生成器（PEP 380），asyncio 的协程就是在这上面长出来的，第 19 章细讲。

迭代器只能走一遍：nums = (x for x in data) 之后先 max(nums) 再 min(nums)，第二次面对的是一个已经走空的迭代器，抛出 ValueError: min() iterable argument is empty。
方括号的列表推导式是急切的：把例子里的圆括号换成 [n for n in counter() if n % 2 == 0]，它会一直向无穷的计数器要数，内存涨到进程被杀为止。
生成器函数体在第一次 next() 时才开始执行：写在函数开头的参数检查不会在调用时报错，例子里的 pulled 在 list() 之前也一直是 0。错误和副作用出现在消费的地方，离写代码的地方可能很远。

JS/TS 怎么做

JavaScript 从 ES2015 起有原生的迭代器协议：迭代器是一个带 next() 方法的对象，next() 返回 { value, done }；可迭代对象有一个键为 Symbol.iterator 的方法，返回迭代器。for...of、展开运算符、解构都走这套协议。同一版本加入了 function* 生成器。ES2025 又在 Iterator.prototype 上加了迭代器辅助方法（iterator helpers）：map、filter、take、drop、flatMap、toArray 等，Node 22 已经提供。

/// <reference lib="esnext.iterator" />
// 上一行打开 ES2025 迭代器辅助方法（filter、map、take）的类型声明；Node 22 运行时已经有这些方法

let pulled = 0; // 源头一共产出了几个数

function* counter(): Generator<number> {
  for (let n = 0; ; n++) {
    // 0、1、2……永不结束
    pulled++;
    yield n; // 交出 n，函数在这里暂停，下次 next() 从这里继续
  }
}

const first5 = counter()
  .filter((n) => n % 2 === 0) // 迭代器辅助方法：返回新的迭代器，此刻什么都没算
  .map((n) => n * n)
  .take(5)
  .toArray(); // 一次次调用 next()，拿够 5 个就停

console.log(`前 5 个偶数的平方：${first5.join(" ")}`);
console.log(`实际从源头取了：${pulled} 个数`);

// 输出：
// 前 5 个偶数的平方：0 4 16 36 64
// 实际从源头取了：9 个数

运行：tsx lazy.ts。第一行的三斜线指令是给类型检查用的：本书校验用的编译目标是 ES2022，默认的类型库里没有 ES2025 的迭代器辅助方法，TS 5.6 起把它们放在 esnext.iterator 这个库里，要显式引用；运行时 Node 22 本来就有，这一行对运行没有影响。

counter() 返回的生成器对象既是迭代器，又继承自 Iterator.prototype，所以能直接链式调用 filter、map、take。每个辅助方法都返回一个新的迭代器，只记住上游和要做的事；toArray() 才开始一次次拉值。take(5) 交出 5 个之后，下一次被调用时不再向上游要值，而是调用上游的 return() 把整条链关掉，生成器里若有 finally，此时就会执行。

底层怎么实现。 V8 把生成器函数编译成带挂起点的字节码。执行到 yield 时，解释器把这一帧的寄存器（局部变量和临时值）复制进生成器对象，记下恢复位置，然后返回；next() 把寄存器搬回来，按记下的位置跳回去继续执行。也就是说，“可恢复的帧”由引擎直接支持。TS 要编译到 ES5 这种没有生成器的目标时做不到这一点，只能把函数体改写成一个带 switch 的状态机函数，每个 yield 是一个分支，局部变量挪到闭包里。

数组的 map、filter 是急切的：arr.map(f).filter(g).slice(0, 5) 面对一百万个元素时，f 被调用一百万次，中间还造出两个大数组，最后只用 5 个。对无穷生成器写 [...counter()] 则永远不会返回。
生成器对象的 [Symbol.iterator]() 返回它自己，所以和 Python 一样只能走一遍；数组每次 for...of 都给一个新迭代器，换成生成器后第二个循环悄悄一次也不执行。
提前退出时，for...of 的 break 会调用迭代器的 return()，生成器的 finally 得以执行；手动调用 next() 拿了几个就扔掉，finally 永远不会执行，里面关闭文件之类的清理就漏掉了。

C# 怎么做

C# 的迭代是原生的：IEnumerable<T> 能给出枚举器，IEnumerator<T> 用 MoveNext() 前进一步、返回有没有下一个，再用 Current 读值，foreach 就建立在这两个接口上。yield return 从 C# 2.0（2005 年）起就有；C# 3.0 带来的 LINQ 是一组 IEnumerable<T> 的扩展方法，默认延迟执行（deferred execution）。

using System;
using System.Collections.Generic;
using System.Linq;

var pulled = 0; // 源头一共产出了几个数

IEnumerable<int> Counter()
{
    for (var n = 0; ; n++) // 0、1、2……永不结束
    {
        pulled++;
        yield return n; // 交出 n，方法在这里暂停，下次 MoveNext() 从这里继续
    }
}

var query = Counter()
    .Where(n => n % 2 == 0) // LINQ 延迟执行：这里只是搭好查询，什么都没算
    .Select(n => n * n)
    .Take(5);
var first5 = query.ToList(); // ToList 一次次调用 MoveNext()，拿够 5 个就停

Console.WriteLine($"前 5 个偶数的平方：{string.Join(" ", first5)}");
Console.WriteLine($"实际从源头取了：{pulled} 个数");

// 输出：
// 前 5 个偶数的平方：0 4 16 36 64
// 实际从源头取了：9 个数

运行：dotnet run lazy.cs。Counter 是一个局部函数，含有 yield return 就成了迭代器方法，还能捕获外面的 pulled。query 只是一个描述“怎样算”的对象，ToList() 才真正执行。C# 的协议分两步：先 MoveNext() 问有没有，再读 Current；Python 和 JS 是一步，靠异常或 done 表示结束。LINQ 还有查询语法 from n in Counter() where n % 2 == 0 select n * n，编译器把它翻译成同样的 Where 和 Select 调用。

底层怎么实现。 运行时不支持暂停一个方法的栈帧，所以 yield return 完全由编译器解决：它把迭代器方法改写成一个隐藏的嵌套类，同时实现 IEnumerable<int> 和 IEnumerator<int>。局部变量变成这个类的字段，一个整数字段记录停在第几个 yield；MoveNext() 是一个大 switch，先按状态跳到上次停下的地方，执行到下一个 yield return n 时把 n 存进 Current、更新状态、返回 true。两次调用之间，进度全在堆上的这个对象里，栈上什么也没留。方法体里的 finally 被编进 Dispose()，foreach 提前退出时会调用它。

LINQ 的 Where、Select、Take 各自返回一个包着上游的迭代器对象。

同一个查询枚举两次就算两遍：先 query.Count() 再 foreach (var x in query)，整条流水线从计数器开始重跑，每枚举一次 pulled 多 9。查询的源头是数据库时，就是两次查询。
迭代器方法里的参数检查被推迟：方法开头写 if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));，调用时不抛，等第一次 MoveNext() 才抛，异常出现在消费处。常见做法是外层写一个普通方法做检查，里面再调用真正带 yield 的局部函数。
查询捕获的是变量，不是值：var limit = 5; var q = xs.Where(x => x < limit); limit = 0; 之后执行 q，用的是 0。

Go 怎么做

Go 没有生成器，没有 yield 关键字。早年的迭代器各写各的：bufio.Scanner 这类带 Scan() 方法的拉取式对象，filepath.Walk 这类接收回调的函数，或者用一个 goroutine 往通道里送值。1.23（2024 年 8 月）统一了写法：for v := range f 可以作用于函数（range-over-func），只要 f 的类型是 func(yield func(V) bool)；iter 包把它命名为 iter.Seq[V]，另有两个值的 iter.Seq2，并提供 iter.Pull 把推送式转成拉取式。maps.Keys、slices.Values 都返回这种迭代器；iter 包只有这几样，没有现成的 Filter、Map，要自己写几行。

package main

import (
  "fmt"
  "iter"
  "strings"
)

var pulled = 0 // 源头一共产出了几个数

func counter() iter.Seq[int] {
  return func(yield func(int) bool) { // yield 返回 false 表示消费者不要了
    for n := 0; ; n++ { // 0、1、2……永不结束
      pulled++
      if !yield(n) {
        return
      }
    }
  }
}

func filter[T any](seq iter.Seq[T], keep func(T) bool) iter.Seq[T] {
  return func(yield func(T) bool) {
    for v := range seq {
      if keep(v) && !yield(v) {
        return
      }
    }
  }
}

func mapSeq[T, U any](seq iter.Seq[T], f func(T) U) iter.Seq[U] {
  return func(yield func(U) bool) {
    for v := range seq {
      if !yield(f(v)) {
        return
      }
    }
  }
}

func main() {
  evens := filter(counter(), func(n int) bool { return n%2 == 0 })
  squares := mapSeq(evens, func(n int) int { return n * n }) // 此刻什么都没算

  var first5 []string
  for v := range squares { // 编译器把循环体包成 yield 回调交给 squares
    first5 = append(first5, fmt.Sprint(v))
    if len(first5) == 5 {
      break // 拿够就停：这个回调返回 false，一路传回 counter
    }
  }
  fmt.Println("前 5 个偶数的平方：" + strings.Join(first5, " "))
  fmt.Printf("实际从源头取了：%d 个数\n", pulled)
}

// 输出：
// 前 5 个偶数的平方：0 4 16 36 64
// 实际从源头取了：9 个数

运行：go run lazy.go。counter、filter、mapSeq 都只是返回一个闭包，搭好时一行也不执行；“取 5 个”由消费者自己 break 完成，用不着单独的 take。控制流和前三种语言正好相反：counter 在最外层循环，每产出一个数就调用 filter 的回调，后者再调用 mapSeq 的回调，最里层才是 main 的循环体。break 让最里层回调返回 false，每一层看到 !yield(...) 就 return，一层层退回到 counter，它的 for 随之结束。

底层怎么实现。 range-over-func 是编译器的改写：for v := range squares { 循环体 } 变成 squares(func(v int) bool { 循环体; return true })。循环体里的 break 变成 return false；return、goto 和带标签的 continue 要跳出循环体之外，编译器另加一个隐藏的状态变量记下要去哪，回调返回 false，等 squares 返回后再按状态执行真正的跳转。全程只是普通的函数调用，没有新的 goroutine，也没有额外的栈；迭代器和循环体都小的时候，编译器有机会把它们内联成接近手写循环的代码。

iter.Pull(seq) 返回 next 和 stop 两个函数，用来同时从两个序列交替取值这类推送式做不到的事。它需要一个能暂停在 yield 里的执行环境，运行时为此在另一个 goroutine 上跑迭代器，并专门实现了协程式的直接切换，不走调度器的常规排队，比通道便宜得多。1.23 之前用通道模拟生成器，每个元素都要两次经过调度器的 goroutine 切换，消费者提前不要了，生产者的 goroutine 就永远阻塞在发送上。

忽略 yield 的返回值：迭代器里只写 yield(n)，消费者 break 后它还继续调用，运行时直接 panic：range function continued iteration after function for loop body returned false。
iter.Pull 用完不调用 stop：没走到序列末尾就扔下，跑迭代器的 goroutine 一直挂着，迭代器里的 defer 也不会执行。紧跟着写 defer stop()。
有的迭代器只能用一次：例子里的 counter() 每次 range 都从 0 重来，从网络或文件读数据的迭代器第二次 range 却接不上开头。iter 包的文档要求这类单次迭代器在注释里写明。

对比表

维度	Python	JS/TS	C#	Go
支持程度	原生	原生	原生	原生（1.23 起）
实现机制	生成器对象保存帧	引擎挂起字节码帧	编译器生成状态机类	回调函数 + 编译器改写循环体
迭代器协议	`__next__` + `StopIteration`	`next()` 返回 `{ value, done }`	`MoveNext()` + `Current`	`func(yield func(V) bool)`
生成器	`def` + `yield`	`function*` + `yield`	`yield return`	没有，写接收回调的函数
惰性流水线的写法	生成器表达式 + `islice`	`.filter().map().take()`	`.Where().Select().Take()`	自己写 `filter`、`mapSeq`
无穷序列	`itertools.count()`	`for (;;) yield n`	`for (;;) yield return n;`	`for { if !yield(n) { return } }`
提前终止	不再调用；`close()` 触发 `finally`	`return()` 触发 `finally`	`Dispose()` 触发 `finally`	回调返回 `false`
从推送转拉取	不需要，本来就是拉取	不需要，本来就是拉取	不需要，本来就是拉取	`iter.Pull` + `defer stop()`

差别最大的是“实现机制”一行：同样是 yield，Python 和 JS 由运行时保存帧，C# 由编译器改写成类；Go 干脆没有可暂停的函数，控制方向也倒了过来。

差异从哪来

生成器的思路很早就有：1970 年代的 CLU 有迭代器，Icon 有生成器。Python 2.2（2001 年）参考 Icon 引入 yield，C# 2.0（2005 年）加入 yield return，JavaScript 的生成器借鉴了 Python，在 ES2015 里标准化。三种语言都选了“可恢复函数”，因为它们的协议本来就是拉取式的：消费者调用 next，迭代器就得记住进度，让程序员手写状态机既啰嗦又容易错，不如让一个函数停在 yield 上，把“停在哪一行”当成进度。具体实现各随运行时：CPython 的帧由解释器自己管理、不在 C 栈上，生成器把帧放进自己的对象里留住即可；V8 把寄存器存进生成器对象；CLR 不支持暂停一个方法，C# 就在编译期把方法拆成类，运行时不必做任何改动。

这个选择后来有了更大的后果：可恢复函数正是异步编程需要的东西。Python 的 asyncio 协程从生成器长出来，C# 的 async/await 用的是和迭代器同一种状态机改写，JS 的 async 函数在引擎里也复用了生成器的挂起和恢复。迭代器上的设计，等于提前给异步铺了路。

Go 一开始就有 goroutine 和通道，早年的看法是用 goroutine 往通道里送值就能当生成器用，不必再加一种可暂停的函数。实践证明这样太贵，还容易漏掉 goroutine。2023 年前后，Go 团队在公开讨论中最终选了回调式迭代器，提案讨论里给出的理由是：推送式迭代器只用到函数、闭包和 return 这些已有的东西，不给语言增加协程语义；它就是一个普通循环，写起来自然；迭代器自己在一个函数里跑完，defer 能照常保证清理。真正需要拉取的少数场合交给 iter.Pull，在库里而不是语法里解决。

后果体现在三处。性能：C# 每次枚举要分配一个状态机对象，每个元素一次接口调用；Python 每个元素都要恢复一次解释器帧；Go 的回调在小迭代器上能被内联。调试：C# 的栈跟踪里出现编译器生成的类名和 MoveNext；Go 的栈跟踪里循环体的帧压在迭代器的帧上面，看起来是迭代器调用了你的代码，事实也正是如此。提前终止：拉取式的消费者直接不再要值即可，但清理要靠 return()、Dispose()、close()；for 循环会自动调用，手动拿值后扔掉时，Python 在垃圾回收时替你关闭生成器，JS 和 C# 则不会。推送式的终止要迭代器配合检查 yield 的返回值，换来的是 defer 一定执行。

旁注：别的语言

Haskell 默认就是惰性求值：每个表达式先只是一个“待算的值”（thunk），用到时才算，所以无穷列表是日常写法，不需要专门的迭代器或生成器。代价是这些待算的值会在内存里堆积，像对一千万个数求和这样的简单代码，写法不当就可能吃掉大量内存，需要用严格版本的函数（如 foldl'）强制及时计算。

take 5 [n * n | n <- [0 ..], even n]   -- [0,4,16,36,64]

实践建议

源头很大、没有尽头，或者只需要前几个结果时，用惰性流水线；数据不多又要反复用，就先物化成列表：list()、toArray()、ToList()、slices.Collect。
同一个迭代器或查询要用两次，先物化一次再用，别指望它能重来：Python 和 JS 的生成器第二次是空的，C# 的查询会整个重算一遍。
参数检查放在生成器外面：外层套一个普通函数先检查，再返回生成器。
Go 里写迭代器每次都检查 yield 的返回值；需要拉取时用 iter.Pull 并紧跟 defer stop()；不需要并发的迭代不要用通道。
生成器里打开文件、连接这类资源时，用 for 循环消费到底或显式关闭，让 finally、Dispose、defer 有机会执行。
迭代器模式已由语言内建，自己的集合写个生成器即可，见设计模式书的迭代器一章；累加的循环可以改成流水线，见重构书的以管道取代循环。

练一练

用 TS 和 Go 各写一个惰性的斐波那契序列：序列本身没有尽头，消费者只取前 10 个，打印一行 前 10 个斐波那契数：0 1 1 2 3 5 8 13 21 34。

提示：TS 用 function* 和一个无限循环，交出当前值后用解构 [a, b] = [b, a + b] 前进；取前 10 个可以用 take，别忘了类型库的引用。Go 返回一个 iter.Seq[int]，每次 yield 后检查返回值；消费者在 range 里数够 10 个就 break。想一想：如果序列不是惰性的，这道题还能写吗？

小结

迭代器协议只有两句话：“给我下一个”和“没有了”；Python、JS、C# 是消费者拉取，Go 1.23 起是迭代器推送。
生成器是可以暂停和恢复的函数：Python 和 JS 由运行时保存帧，C# 由编译器改写成状态机类；Go 没有生成器，用接收 yield 回调的函数代替，iter.Pull 再转成拉取式。
惰性流水线搭好时什么也不算，消费者每要一个值，请求才往上游传一格，所以能处理无穷序列；数组的 map、filter 和列表推导式是急切的。
惰性带来延迟：生成器体和 LINQ 查询到第一次取值才执行，参数检查随之推迟；生成器只能走一遍，查询每走一遍都重算。
提前终止各有其法：return()、Dispose()、close() 触发清理，Go 靠 yield 返回 false 加 defer。