4.2 隐序列

可以表示一个序列，而不必将每个元素显式地存储在计算机的内存中。 也就是说，我们可以构造一个对象，该对象提供对某些连续数据集的所有元素的访问，而不需要预先计算每个元素的值。 相反，我们根据需要计算元素。

在第2章中介绍的range容器类型中有一个例子。 一个范围表示一个连续的、有界的整数序列。 然而，并不是这个序列的每个元素都显式地表示在内存中。 相反，当从范围中请求元素时，将计算该元素。 因此，我们可以表示非常大范围的整数，而不需要使用大的内存块。 只有范围的端点被存储为范围对象的一部分。

>>> r = range(10000, 1000000000)
>>> r[45006230]
45016230

在本例中，在构造range实例时，并不是存储该范围内的所有999,990000个整数。相反，range对象将第一个元素10,000添加到索引45,006,230以生成元素45,016,230。按需计算值，而不是从现有表示中检索值，是惰性计算的一个例子。在计算机科学中，惰性计算指的是延迟某个值的计算，直到该值需要时才计算的程序。

4.2.1 迭代器

Python和许多其他编程语言提供了一种按顺序处理容器值元素的统一方法，称为迭代器。迭代器是一个对象，它提供对值的一个接一个顺序访问。

迭代器抽象有两个组件：一种机制用于检索正在处理的序列中的下一个元素，另一种机制用于通知已经到达序列的末尾且不再有其他元素存在。对于任何容器，比如列表或范围，都可以通过调用内置的iter函数来获得迭代器。可以通过调用内置的next函数来访问迭代器的内容。

>>> primes = [2, 3, 5, 7]
>>> type(primes)
>>> iterator = iter(primes)
>>> type(iterator)
>>> next(iterator)
2
>>> next(iterator)
3
>>> next(iterator)
5

Python表示没有更多可用值的方式是在调用next时引发StopIteration异常。可以使用try语句处理此异常。

>>> next(iterator)
7
>>> next(iterator)
Traceback (most recent call last):
  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)  # 1st iterator over r
>>> next(s)
3
>>> next(s)
4
>>> t = iter(r)  # 2nd iterator over r
>>> next(t)
3
>>> next(t)
4
>>> u = t        # Alternate name for the 2nd iterator
>>> next(u)
5
>>> next(u)
6

向前移动第二个迭代器不会影响第一个迭代器。因为从第一个迭代器返回的最后一个值是4，所以它被定位为next返回5。另一方面，第二个迭代器被定位为返回7 next。

>>> next(s)
5
>>> next(t)
7

在迭代器上调用iter将返回该迭代器，而不是副本。Python中包含了这种行为，这样程序员就可以对一个值调用iter来获得迭代器，而不必担心它是迭代器还是容器。

>>> v = iter(t)  # Another alterante name for the 2nd iterator
>>> next(v)
8
>>> next(u)
9
>>> next(t)
10

迭代器的有用性源于这样一个事实：迭代器的底层数据序列不能显式地表示在内存中。 迭代器提供了一种机制，可以依次考虑一系列的值，但不需要同时存储所有这些元素。 相反，当从迭代器请求下一个元素时，可以根据需要计算该元素，而不是从现有的内存源检索该元素。

范围能够惰性地计算序列的元素，因为所表示的序列是一致的，而且从范围的起始和结束边界计算任何元素都很容易。 迭代器允许延迟生成更广泛的底层序列数据集，因为它们不需要提供对底层序列的任意元素的访问。 相反，迭代器只需要在每次请求另一个元素时依次计算序列的下一个元素。 虽然不像访问序列的任意元素那样灵活(称为随机访问)，但对顺序数据的顺序访问通常对于数据处理应用程序来说已经足够了。

4.2.2 可迭代对象

任何可以产生迭代器的值都称为可迭代值。 在Python中，可迭代值是任何可以传递给内置iter函数的值。 可迭代对象包括序列值，如字符串和元组，以及其他容器，如集合和字典。迭代器也是可迭代对象，因为它们可以传递给iter函数。

即使是字典之类的无序集合在生成迭代器时也必须对其内容定义顺序。 字典和集合是无序的，因为程序员无法控制迭代的顺序，但是Python在其规范中保证了它们的某些属性的顺序。

TODO块引用

>>> 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)
       
RuntimeError: dictionary changed size during iteration
Traceback (most recent call last):

4.2.3 内置迭代器

一些内置函数接受可迭代值作为参数并返回迭代器。 这些函数广泛用于延迟序列处理。

map函数是惰性的：调用它并不执行计算其结果元素所需的计算。 相反，将创建一个迭代器对象，如果使用next进行查询，该对象将返回结果。 我们可以在下面的例子中观察到这一事实，在这个例子中，对print的调用被延迟，直到double迭代器请求相应的元素。

>>> 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 not yet called
>>> next(doubled)                       # double_and_print called once
*** 3 => 6 ***
6
>>> next(doubled)                       # double_and_print called again
*** 4 => 8 ***
8
>>> list(doubled)                       # double_and_print called twice more
*** 5 => 10 ***
*** 6 => 12 ***
[10, 12]

filter函数返回一个迭代器over, zip，而reverse函数也返回迭代器。 TODO演示这些值

4.2.4 For语句

Python中的for语句操作迭代器。如果对象具有返回迭代器的__iter__方法，则该对象是可迭代的(接口)。可迭代对象可以是for语句头中的<expression>的值:

for <name> in <expression>:
    <suite>

为了执行for语句，Python计算头文件<expression>，它必须产生一个可迭代值。然后，对该值调用__iter__方法。在引发StopIteration异常之前，Python会反复调用该迭代器上的__next__方法，并将结果绑定到for语句中的。然后，它执行<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异常的handling子句不做任何事情，但是处理异常提供了退出while循环的控制机制。

要在for循环中使用迭代器，迭代器还必须具有__iter__方法。迭代器类型 Python文档建议迭代器有一个' _iter '方法，该方法返回迭代器本身，因此所有迭代器都是可迭代的。

4.2.5 生成器和Yield声明

Letters和 Positives对象要求我们引入一个新的概念 self.current到我们的对象，以跟踪序列的进程。 使用上面所示的简单序列，这可以很容易地完成。 然而，对于复杂的序列，__next__方法在计算中保存自己的位置可能会相当困难。生成器允许我们利用Python解释器的特性来定义更复杂的迭代。

生成器是由称为生成器函数的特殊函数类返回的迭代器。 生成器函数与常规函数的区别在于，它们不在函数体中包含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

尽管我们从未显式定义__iitem__或__next__方法，但yield语句表明我们正在定义一个生成器函数。 当被调用时，生成器函数不会返回特定的生成值，而是返回自身可以返回生成值的生成器(它是一种迭代器类型)。 生成器对象有__item__和__next__方法，每次对__next__的调用都会从它之前停止的地方继续执行生成器函数，直到执行另一个yield语句。

第一次调用__next__时，程序从letters_generator函数体开始执行语句，直到遇到yield语句为止。然后，它暂停并返回current.yeild的值，不会破坏新创建的环境，它们会保存它以供以后使用。当__next__再次被调用时，执行将在它停止的地方继续。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__方法被调用时返回一个迭代器。可迭代值表示数据集合，它们提供了一种固定的表示方式，可以产生多个迭代器。

例如，下面的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'

可迭代字母实例b_to_k和Letters迭代器实例first_iterator和second_iterator的不同之处在于，Letters实例不会改变，而迭代器实例在每次调用next时都会改变(或等价地，每次调用__next__时)。 迭代器通过顺序数据跟踪进度，而迭代器表示数据本身。

Python中的许多内置函数接受可迭代参数并返回迭代器。 例如，map函数接受一个函数和一个可迭代对象。 它将函数实参应用于iterable实参中的每个元素后的结果返回一个迭代器。

>>> 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中的iterable接口由单个消息__iter__组成，该消息返回一个迭代器。 Python中的内置序列类型在调用其__iter__方法时返回迭代器的新实例。 如果一个可迭代对象在每次__iter__被调用时都返回一个新的迭代器实例，那么它可以被多次迭代。

通过实现iterable接口可以定义新的iterable类。 例如，下面的可迭代类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__方法是一个生成器函数；它返回一个generator对象，生成字母'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__将返回基础序列的顺序元素。 Python通过在调用__next__期间引发StopIteration异常来指示已经到达底层序列的结束。

下面的LetterIter类迭代一系列基础字母，从某个起始字母到但不包括某个结束字母。 实例属性nextletter存储要返回的下一个字母。 ___next__方法返回这个字母并使用它来计算一个新的next_letter。

>>> class LetterIter:
        """An iterator over letters of the alphabet in ASCII order."""
        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

迭代器是可变的：它们跟踪某个底层值序列中的位置。 当到达end时，迭代器就用完。 LetterIter实例只能遍历一次。 在它的__next__()方法引发StopIteration异常后，它将继续这样做。 通常，迭代器不会被重置；相反，创建一个新实例来开始新的迭代。

迭代器还允许我们通过实现永不引发StopIteration异常的__next__方法来表示无穷级数。 例如，下面的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)
3

4.2.9 流

待办事项

4.2.10 Python流

流提供了另一种隐式表示顺序数据的方式。 流是一个延迟计算的链表。 与第2章中的Link类一样，流实例响应对其第一个元素和流其余部分的请求。 像链接一样，流的其余部分本身就是一个流。 与链接不同，流的其余部分仅在查找时才计算，而不是预先存储。 也就是说，流的其余部分是惰性计算的。

为了实现这种延迟求值，流存储一个函数来计算流的其余部分。 无论何时调用这个函数，它的返回值都会作为流的一部分缓存到一个名为_rest的属性中，该属性带有下划线表示不应该直接访问它。

可访问属性rest是一个属性方法，它返回流的其余部分，并在必要时进行计算。 通过这种设计，流存储了如何计算流的其余部分，而不是总是显式地存储其余部分。

>>> class Stream:
        """A lazily computed linked list."""
        class empty:
            def __repr__(self):
                return 'Stream.empty'
        empty = empty()
        def __init__(self, first, compute_rest=lambda: empty):
            assert callable(compute_rest), 'compute_rest must be callable.'
            self.first = first
            self._compute_rest = compute_rest
        @property
        def rest(self):
            """Return the rest of the stream, computing it if necessary."""
            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))

链表使用嵌套表达式定义。例如，我们可以创建一个链接来表示元素1和5，如下所示：

>>> r = Link(1, Link(2+3, Link(9)))

同样，我们可以创建表示相同系列的流。在请求流的其余部分之前，流实际上不会计算第二个元素5。我们通过创建匿名函数来实现这个效果。

>>> s = Stream(1, lambda: Stream(2+3, lambda: Stream(9)))

在这里，1是流的第一个元素，后面的lambda表达式返回一个函数，用于计算流的其余部分。

访问链表r和流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的其余部分包括一个计算其余部分的函数；它将返回空流的事实可能还没有被发现。

当一个流实例被构造时，字段self. _rest为None，表示流的其余部分还没有计算。 当通过点表达式请求rest属性时，将调用rest属性方法，该方法将用self触发计算。 _rest = self._compute_rest()。 由于流中的缓存机制，compute_rest函数只被调用一次，然后被丢弃。

compute_rest函数的基本属性是它不接受参数，并返回一个流或Stream.empty。

惰性计算使我们能够使用流来表示无限的连续数据集。 例如，我们可以表示递增的整数，从第一个值开始。

>>> 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第一次被调用时，它返回一个流，其first是序列中的第一个整数。 然而，integer_stream实际上是递归的，因为此流的compute_rest再次调用integer_stream，并带有一个递增的参数。 我们说integer_stream是惰性的，因为只有当整数流的其余部分被请求时，才会对integer_stream进行递归调用。

>>> positives.first
1
>>> positives.rest.first
2
>>> positives.rest.rest
Stream(3, <...>)

操作序列的高阶函数map和filter也适用于流，尽管它们的实现必须更改以惰性地应用它们的参数函数。函数map_stream将一个函数映射到一个流上，从而生成一个新的流。本地定义的compute_rest函数确保在计算其余部分时将该函数映射到流的其余部分。

>>> 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)

可以通过定义compute_rest函数来过滤流，该函数将filter函数应用于流的其余部分。如果筛选器函数拒绝流的第一个元素，则立即计算其余元素。因为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函数在流处理中表现出一种常见的模式：本地定义的compute_rest函数在计算流的其余部分时递归地应用处理函数。

要检查流的内容，可以对Python列表强制执行前k个元素。

>>> 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)
>>> m
Stream(9, <...>)
>>> first_k_as_list(m, 5)
[9, 16, 25, 36, 49]

可以使用filter_stream函数使用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

就像链表提供了序列抽象的简单实现一样，流提供了一个简单的、函数式的、递归的数据结构，通过使用高阶函数实现了延迟求值。