4.2 隐式序列
序列（sequence）的表示，不必把每个元素都显式地存进计算机内存。也就是说，我们可以构造一个对象，它提供对某个序列数据集里所有元素的访问，却不必提前算出每个元素的值；元素在需要时才计算。
第 2 章介绍的 range 容器类型就体现了这一思想。一个 range 表示一个有界的连续整数序列，但它的每个元素并不是显式地存在内存里。当从 range 中请求一个元素时，它才被计算出来。因此，我们能表示非常大的整数范围，而不占用大块内存：range 对象里只存了序列的端点。
>>> r = range(10000,1000000000)
>>> r[45006230]
45016230在这个例子中，构造 range 实例时，并没有把这 999,990,000 个整数全部存起来。range 对象只是把起始元素 10,000 加上索引 45,006,230，得到元素 45,016,230。在需要时才计算值，而不是从已有的表示里检索值，这就是惰性计算（lazy computation）的一个例子。在计算机科学中，惰性计算指任何把值的计算推迟到真正需要时才进行的程序。
4.2.1 迭代器
Python 和许多其他编程语言都提供了一种统一的方式，用来依次处理容器值里的元素，叫做迭代器（iterator）。迭代器是一个对象，能逐个提供对值的顺序访问。
迭代器抽象包含两部分：一是取出所处理序列中下一个元素的机制，二是表明序列已到末尾、没有更多元素的信号机制。任何容器，比如 list 或 range，都能调用内置的 iter 函数得到迭代器；迭代器的内容则用内置的 next 函数访问。
>>> primes = [2, 3, 5, 7]
>>> type(primes)
<class 'list'>
>>> iterator = iter(primes)
>>> type(iterator)
<class 'list-iterator'>
>>> next(iterator)
2
>>> next(iterator)
3
>>> next(iterator)
5Python 表示没有更多可用值的方式，是在调用 next 时抛出 StopIteration 异常。这个异常可以用 try 语句处理。
>>> next(iterator)
7
>>> next(iterator)
Traceback (most recent call las):
File "<stdin>", line 1, in <module>
StopIteration
>>> try:
next(iterator)
except StopIteration:
print('No more values')
No more values迭代器维护局部状态，来表示自己在序列中的位置。每次调用 next，这个位置就向前推进。两个彼此独立的迭代器可以跟踪同一序列中的两个不同位置；但同一个迭代器的两个名称会共享同一个位置，因为它们共享同一个值。
>>> r = range(3, 13)
>>> s = iter(r) # r 的第一个迭代器
>>> next(s)
3
>>> next(s)
4
>>> t = iter(r) # r 的第二个迭代器
>>> next(t)
3
>>> next(t)
4
>>> u = t # u 绑定到 r 的第二个迭代器
>>> next(u)
5
>>> next(u)
6推进第二个迭代器不会影响第一个。第一个迭代器最后返回的值是 4，所以下一次会返回 5；而第二个迭代器下一次会返回 7。
>>> next(s)
5
>>> next(t)
7对一个迭代器调用 iter，返回的是它本身，而不是副本。Python 之所以有这样的行为，是为了让程序员对任何值调用 iter 都能得到迭代器，不必操心拿到的是迭代器还是容器。
>>> v = iter(t) # v 绑定到 r 的第二个迭代器
>>> next(v) # u, v, t 都为 r 的第二个迭代器
8
>>> next(u)
9
>>> next(t)
10迭代器之所以有用，是因为它背后的数据系列未必在内存中显式表示。迭代器提供了一种机制，能逐个考虑一系列的值，而不必把这些元素同时存下来；当向迭代器请求下一个元素时，这个元素可以现算出来，而不是从已有的内存里取。
range 能惰性地计算序列元素，是因为它表示的序列是均匀的，任何元素都能从范围的起止端点轻易算出。迭代器则能惰性地生成范围广得多的一类底层序列数据，因为它不需要提供对底层系列中任意元素的访问，只需按顺序算出系列的下一个元素，每请求一个元素就算一个。这种顺序访问虽然不如访问序列的任意元素（称为随机访问（random access））灵活，但对数据处理应用来说，对连续数据的顺序访问（sequential access）通常已经够用。
4.2.2 可迭代对象
任何能产生迭代器的值都称为可迭代值（iterable value）。在 Python 中，可迭代值是任何能传给内置 iter 函数的值。
可迭代对象包括：
- 序列值：比如字符串（string）和元组（tuple）
- 容器：比如集合（set）和字典（dictionary）
迭代器也是可迭代的，因为它们能传给 iter 函数。
即使是字典这样的无序容器，在生成迭代器时也必须给其内容定一个顺序。字典和集合是无序的，因为程序员无法控制迭代顺序，但 Python 确实在规范里对它们的顺序作了某些保证。
>>> d = {'one': 1, 'two': 2, 'three': 3}
>>> d
{'one': 1, 'three': 3, 'two': 2}
>>> k = iter(d)
>>> next(k)
'one'
>>> next(k)
'three'
>>> v = iter(d.values())
>>> next(v)
1
>>> next(v)
3如果字典因添加或删除键而改变了结构，那么所有迭代器都会失效，后续迭代器所呈现的内容顺序也可能任意变化。另一方面，修改某个已有键的值，不会改变内容顺序，也不会让迭代器失效。
>>> d.pop('two')
2
>>> next(k)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
RuntimeError: dictionary changed size during iteration4.2.3 内置迭代器
有几个内置函数接受可迭代值作为参数，返回迭代器。这些函数广泛用于惰性序列处理。
map 函数是惰性的：调用它并不会执行计算结果元素所需的运算。它只是创建一个迭代器对象，用 next 查询时才会返回结果。下面的例子就说明了这一点：对 print 的调用被推迟，直到从 doubled 迭代器请求相应元素时才发生。
>>> def double_and_print(x):
print('***', x, '=>', 2*x, '***')
return 2*x
>>> s = range(3, 7)
>>> doubled = map(double_and_print, s) # double_and_print 未被调用
>>> next(doubled) # double_and_print 调用一次
*** 3 => 6 ***
6
>>> next(doubled) # double_and_print 再次调用
*** 4 => 8 ***
8
>>> list(doubled) # double_and_print 再次调用兩次
*** 5 => 10 *** # list() 会把剩余的值都计算出来并生成一个列表
*** 6 => 12 ***
[10, 12]filter 函数返回一个迭代器，zip 和 reversed 函数也返回迭代器。
4.2.4 For 语句
Python 中的 for 语句是对迭代器操作的。如果对象具有返回迭代器的 __iter__ 方法（method），它就是可迭代的。可迭代对象可以作为 for 语句头部 <expression> 的值：
for <name> in <expression>:
<suite>执行 for 语句时，Python 会先求值头部的 <expression>，其值必须是可迭代的。然后，它对这个值调用 __iter__ 方法。在抛出 StopIteration 异常之前，Python 会反复调用该迭代器上的 __next__ 方法，并把结果绑定到 for 语句里的 <name>，然后执行 <suite>。
>>> counts = [1, 2, 3]
>>> for item in counts:
print(item)
1
2
3在上面的例子中，counts 列表通过它的 __iter__() 方法返回一个迭代器。for 语句随后反复调用该迭代器的 __next__() 方法，每次把返回的值赋给 item。这个过程一直持续到迭代器抛出 StopIteration 异常，此时 for 语句的执行就结束了。
有了前面关于迭代器的知识，我们现在可以用 while、赋值和 try 语句来实现 for 语句的执行规则。
>>> items = counts.__iter__()
>>> try:
while True:
item = items.__next__()
print(item)
except StopIteration:
pass
1
2
3上例中，调用 counts 的 __iter__ 方法得到的迭代器绑定到名称 items，这样就可以依次查询每个元素。处理 StopIteration 异常的子句什么也不做，但处理这个异常提供了一种退出 while 循环的控制机制。
要在 for 循环中使用迭代器，迭代器还必须具有 __iter__ 方法。Python 文档的迭代器类型一节建议，迭代器应带有返回迭代器本身的 __iter__ 方法，这样所有迭代器就都是可迭代的。
4.2.5 生成器和 Yield 语句
上面提到的 Letters 和 Positives 对象，要求我们在对象里引入一个新字段（field）self.current，用来跟踪推进到序列的哪里。对于像上面这样的简单序列，这很容易做到；但对于复杂序列，__next__ 方法要在计算过程中记住自己走到哪一步，可能相当困难。生成器（generator）让我们能借助 Python 解释器（interpreter）的特性，定义更复杂的迭代。
生成器是由一种特殊函数——生成器函数（generator function）——返回的迭代器。生成器函数和普通函数的不同之处在于，它的函数体里不含 return 语句，而是用 yield 语句返回一系列元素。
生成器不用对象的属性来跟踪自己在序列中的进度，而是控制生成器函数的执行：每次调用生成器的 __next__ 方法时，函数都会一直运行到下一个 yield 语句执行完为止。用生成器函数实现 Letters 迭代器要简洁得多。
>>> def letters_generator():
current = 'a'
while current <= 'd':
yield current
current = chr(ord(current) + 1)
>>> for letter in letters_generator():
print(letter)
a
b
c
d即使我们从未显式定义 __iter__ 或 __next__ 方法，yield 语句也表明我们定义的是一个生成器函数。调用生成器函数时，它返回的不是某个具体的产出值，而是一个生成器（一种迭代器），由这个生成器来返回各个产出值。生成器对象有 __iter__ 和 __next__ 方法，每次调用 __next__ 都会从上次离开的地方继续执行生成器函数，直到下一个 yield 语句执行完为止。
第一次调用 __next__ 时，程序执行 letters_generator 函数体里的语句，直到遇到 yield 语句。然后它暂停，返回 current 的值。yield 语句不会销毁新建的环境，而是把它保留下来供以后使用。再次调用 __next__ 时，执行会从上次离开的地方继续。current 的值，以及 letters_generator 作用域内其他已绑定名称的值，在后续多次调用 __next__ 时都会保留。
我们可以手动调用 __next__() 来遍历生成器：
>>> letters = letters_generator()
>>> type(letters)
<class 'generator'>
>>> letters.__next__()
'a'
>>> letters.__next__()
'b'
>>> letters.__next__()
'c'
>>> letters.__next__()
'd'
>>> letters.__next__()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration生成器在第一次调用 __next__ 之前，不会执行生成器函数体内的任何语句。只要生成器函数返回，生成器就抛出 StopIteration 异常。
4.2.6 可迭代接口
如果一个对象调用 __iter__ 方法会返回迭代器，它就是可迭代的（iterable）。可迭代值表示数据集合，它提供的是一种固定的表示，可以产生多个迭代器。
例如，下面 Letters 类的实例表示一段连续字母的序列。每次调用它的 __iter__ 方法，都会构造一个新的 LetterIter 实例，用来顺序访问序列的内容。
>>> class Letters:
def __init__(self, start='a', end='e'):
self.start = start
self.end = end
def __iter__(self):
return LetterIter(self.start, self.end)内置 iter 函数会在其参数上调用 __iter__ 方法。在下面的表达式序列中，由同一个可迭代序列衍生出的两个迭代器各自独立地按顺序产生字母。
>>> b_to_k = Letters('b', 'k')
>>> first_iterator = b_to_k.__iter__()
>>> next(first_iterator)
'b'
>>> next(first_iterator)
'c'
>>> second_iterator = iter(b_to_k)
>>> second_iterator.__next__()
'b'
>>> first_iterator.__next__()
'd'
>>> first_iterator.__next__()
'e'
>>> second_iterator.__next__()
'c'
>>> second_iterator.__next__()
'd'可迭代的 Letters 实例 b_to_k，和 LetterIter 迭代器实例 first_iterator、second_iterator，区别在于：Letters 实例不会变化，而迭代器实例每调用一次 next（等价地说，每调用一次 __next__）都会变化。迭代器跟踪在顺序数据中的进度，而可迭代对象表示的是数据本身。
Python 中许多内置函数接受可迭代参数，返回迭代器。例如 map 函数接受一个函数和一个可迭代对象，它返回的迭代器会逐项给出把函数参数施加到可迭代参数中每个元素上的结果。
>>> caps = map(lambda x: x.upper(), b_to_k)
>>> next(caps)
'B'
>>> next(caps)
'C'4.2.7 用 Yield 创建可迭代对象
在 Python 中，迭代器只对底层数据系列遍历一遍。遍历过一遍之后，再调用 __next__()，迭代器会一直抛出 StopIteration 异常。许多应用需要多次迭代元素。例如，要枚举一个列表中所有的元素对，就必须多次遍历这个列表。
>>> def all_pairs(s):
for item1 in s:
for item2 in s:
yield (item1, item2)
>>> list(all_pairs([1, 2, 3]))
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), ( 3, 3)]序列本身不是迭代器，而是可迭代对象。Python 中可迭代接口只包含一个消息 __iter__，它返回一个迭代器。Python 的内置序列类型在调用 __iter__ 方法时会返回新的迭代器实例。如果一个可迭代对象每次调用 __iter__ 都返回一个新的迭代器实例，它就可以被多次迭代。
实现可迭代接口，就能定义新的可迭代类。例如，下面这个可迭代的 LettersWithYield 类，每次调用 __iter__ 都会返回一个遍历字母的新迭代器。
>>> class LettersWithYield:
def __init__(self, start='a', end='e'):
self.start = start
self.end = end
def __iter__(self):
next_letter = self.start
while next_letter < self.end:
yield next_letter
next_letter = chr(ord(next_letter) + 1)__iter__ 方法是一个生成器函数；它返回一个生成器对象，产出字母「a」到「d」，然后停止。每次调用这个方法，都会有一个新生成器重新从头遍历这些顺序数据。
>>> letters = LettersWithYield()
>>> list(all_pairs(letters))[:5]
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a') ]4.2.8 迭代器接口
Python 的迭代器接口由一个名为 __next__ 的方法定义，它返回所表示的底层连续序列的下一个元素。收到 __next__ 调用时，迭代器可以执行任意计算，以检索或算出下一个元素。调用 __next__ 会对迭代器做出修改：推进它的位置。因此，多次调用 __next__ 会返回底层序列中连续的元素。在调用 __next__ 的过程中抛出 StopIteration 异常，就表示底层序列已经到末尾。
下面的 LetterIter 类，遍历从某个起始字母到某个结束字母（不含结束字母）的一系列字母。实例属性 next_letter 保存下一个要返回的字母；__next__ 方法返回这个字母，并用它算出新的 next_letter。
>>> class LetterIter:
"""依照 ASCII 码值顺序迭代字符的迭代器。"""
def __init__(self, start='a', end='e'):
self.next_letter = start
self.end = end
def __next__(self):
if self.next_letter == self.end:
raise StopIteration
letter = self.next_letter
self.next_letter = chr(ord(letter)+1)
return letter利用这个类，可以用下面两种方式按顺序访问字母：
__next__方法next()内置函数（其实也是调用__next__）
>>> letter_iter = LetterIter()
>>> letter_iter.__next__()
'a'
>>> letter_iter.__next__()
'b'
>>> next(letter_iter)
'c'
>>> letter_iter.__next__()
'd'
>>> letter_iter.__next__()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 12, in next
StopIteration迭代器是可变的：它们随着前进记录自己在底层序列中的位置。到达末尾后，这个迭代器就用完了。一个 LetterIter 实例只能遍历一次；它的 __next__() 方法抛出 StopIteration 异常之后，再调用也一直会抛出这个异常。
通常，迭代器不会被重置；要开始新的迭代，就创建一个新实例。
迭代器还能表示无限级数：只要实现的 __next__ 方法永远不抛出 StopIteration 异常即可。例如，下面的 Positives 类迭代无限的正整数序列。Python 内置的 next 函数会在其参数上调用 __next__ 方法。
>>> class Positives:
def __init__(self):
self.next_positive = 1;
def __next__(self):
result = self.next_positive
self.next_positive += 1
return result
>>> p = Positives()
>>> next(p)
1
>>> next(p)
2
>>> next(p)
34.2.9 流
译注：原书此节尚未完成，暂无正文。
4.2.10 Python 流
流（stream）提供了另一种隐式表示连续数据的方式。一个 Stream 是一个惰性计算的链表（linked list）。和第 2 章的 Link 类一样，Stream 实例会响应关于它的第一个元素和其余部分的请求。和 Link 一样，Stream 的其余部分本身也是一个 Stream；但与 Link 不同，Stream 的其余部分只在被查找时才计算，而不是提前存下来。也就是说，Stream 的其余部分是惰性计算的。
为了实现这种惰性求值（lazy evaluation），Stream 存了一个计算其余部分的函数。每次调用这个函数，它的返回值都会作为 Stream 的一部分缓存起来，存到一个名为 _rest 的属性里，用下划线命名，表示不应直接访问。
可访问的 rest 属性是一个属性方法，它返回流的其余部分，必要时才计算它。这种设计让 Stream 存的是「如何计算」其余部分，而不是总把其余部分显式存下来。
>>> class Stream:
"""惰性计算的链表"""
class empty:
def __repr__(self):
return 'Stream.empty'
empty = empty()
def __init__(self, first, compute_rest=lambda: empty):
assert callable(compute_rest), 'compute_rest 必须为可调用'
self.first = first
self._compute_rest = compute_rest
@property
def rest(self):
"""返回 Stream 的其他部分（缓存部分），如果需要计算，则计算"""
if self._compute_rest is not None:
self._rest = self._compute_rest()
self._compute_rest = None
return self._rest
def __repr__(self):
return 'Stream({0}, <...>)'.format(repr(self.first))链表用嵌套表达式定义。例如，可以创建一个 Link，表示依次为 1、5 的元素：
>>> r = Link(1, Link(2 + 3, Link(9)))同样，可以创建一个表示同一系列的 Stream。在请求 Stream 的其余部分之前，Stream 实际上不会计算第二个元素 5。这种效果靠创建匿名函数实现。
s = Stream(1, lambda: Stream(2 + 3, lambda: Stream(9)))这里，1 是 Stream 的第一个元素，后面的 lambda 表达式返回一个计算 Stream 其余部分的函数。
访问链表 r 和 Stream s 的元素，过程类似。不过，5 是存在 r 里的，而在 s 中，它是第一次被请求时用加法现算出来的。
>>> r.first
1
>>> s.first
1
>>> r.rest.first
5
>>> s.rest.first
5
>>> r.rest
Link(5, Link(9))
>>> s.rest
Stream(5, <...>)r 的其余部分是一个两元素链表，而 s 的其余部分包含一个计算其余部分的函数；它最终会返回空流（empty stream），不过这一点也许还没有被发现。
构造 Stream 实例时，字段 self._rest 为 None，表示 Stream 的其余部分尚未计算。用点表达式请求 rest 属性时，会调用 rest 属性方法，触发 self._rest = self._compute_rest() 的计算。由于 Stream 内部的缓存机制，compute_rest 函数只会被调用一次，随后就被丢弃。
compute_rest 函数的本质性质有两点：不接受参数，返回 Stream 或 Stream.empty。
惰性求值让我们能用 Stream 表示无限的连续数据集。例如，我们可以表示从任意起始值开始的递增整数序列。
>>> def integer_stream(first):
def compute_rest():
return integer_stream(first+1)
return Stream(first, compute_rest)
>>> positives = integer_stream(1)
>>> positives
Stream(1, <...>)
>>> positives.first
1第一次调用 integer_stream 时，它返回一个 Stream，其第一个元素是序列中的第一个整数。不过，integer_stream 其实是递归的，因为这个 Stream 的 compute_rest 会用递增后的参数再次调用 integer_stream。我们说 integer_stream 是惰性的，因为只有当请求某个整数流的 rest 时，才会递归调用 integer_stream。
>>> positives.first
1
>>> positives.rest.first
2
>>> positives.rest.rest
Stream(3, <...>)操作序列的那两个高阶函数 map 和 filter，同样适用于 Stream，不过它们的实现必须修改，以便惰性地施加各自的参数函数。
map_stream 把一个函数映射到一个 Stream 上，产生一个新的 Stream；局部定义的 compute_rest 函数保证，每当计算其余部分时，都会把这个函数映射到 Stream 的其余部分上。
>>> def map_stream(fn, s):
if s is Stream.empty:
return s
def compute_rest():
return map_stream(fn, s.rest)
return Stream(fn(s.first), compute_rest)过滤 Stream 的方法是定义一个 compute_rest 函数，把过滤函数施加到 Stream 的其余部分上。如果过滤函数拒绝了 Stream 的第一个元素，就立即计算其余部分。由于 filter_stream 是递归的，其余部分可能被计算多次，直到找到一个有效的第一个元素。
>>> def filter_stream(fn, s):
if s is Stream.empty:
return s
def compute_rest():
return filter_stream(fn, s.rest)
if fn(s.first):
return Stream(s.first, compute_rest)
else:
return compute_rest()map_stream 和 filter_stream 展示了 Stream 处理中的常见模式：每当计算其余部分时，局部定义的 compute_rest 函数都会递归地把处理函数施加到 Stream 的其余部分上。
要检查 Stream 的内容，可以把前面 k 个元素转成 Python 列表。
>>> def first_k_as_list(s, k):
first_k = []
while s is not Stream.empty and k > 0:
first_k.append(s.first)
s, k = s.rest, k - 1
return first_k这些便利函数让我们能用一个简单的例子验证 map_stream 的实现：把 3 到 7 的整数平方。
>>> s = integer_stream(3) # 创建整数流
>>> s
Stream(3, <...>)
>>> m = map_stream(lambda x: x*x, s) # 把 fn, s 传入 map_stream 来得到新的流
>>> m
Stream(9, <...>)
>>> first_k_as_list(m, 5) # 检查前五项
[9, 16, 25, 36, 49]可以用 filter_stream 函数配合埃拉托斯特尼筛法（sieve of Eratosthenes）定义一个质数流。这种方法过滤一个整数流，把所有是首个元素倍数的数字去掉；依次用每个质数过滤，就能把所有合数从流中剔除。
>>> def primes(pos_stream):
def not_divible(x):
return x % pos_stream.first != 0
def compute_rest():
return primes(filter_stream(not_divible, pos_stream.rest))
return Stream(pos_stream.first, compute_rest)截断质数流，就能枚举出质数序列的任意前缀。
>>> prime_numbers = primes(integer_stream(2))
>>> first_k_as_list(prime_numbers, 7)
[2, 3, 5, 7, 11, 13, 17]流与迭代器的区别在于，流可以多次传给纯函数，每次得到的结果都相同。把质数流转成列表，它也不会被「用完」。也就是说，把流的前缀转成列表之后，prime_numbers 的第一个元素仍然是 2。
>>> prime_numbers.first
2正如链表为序列抽象提供了一种简单的实现，流也提供了一种简单、函数式、递归的数据结构，用高阶函数实现惰性求值。