SICP Python 中文版

5.2 隱式序列

序列可以使用一種程序結構來表示，它不將每個元素顯式儲存在內存中，這是高效處理有序數據的核心概念。為了將這個概念用於實踐，我們需要構造對象來提供序列中所有元素的訪問，但是不要事先把所有元素計算出來並儲存。

這個概念的一個簡單示例就是第二章出現的range序列類型。range表示連續有界的整數序列。但是，它的每個元素並不顯式在內存中表示，當元素從range中獲取時，才被計算出來。所以，我們可以表示非常大的整數範圍。只有範圍的結束位置才被儲存為range對象的一部分，元素都被憑空計算出來。

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

這個例子中，當構造範圍示例時，並不是這個範圍內的所有 999,990,000 個整數都被儲存。反之，範圍對象將第一個元素 10,000 與下標相加 45,006,230 來產生第 45,016,230 個元素。計算所求的元素值並不從現有的表示中獲取，這是惰性計算的一個例子。計算機科學將惰性作為一種重要的計算工具加以讚揚。

迭代器是提供底層有序數據集的有序訪問的對象。迭代器在許多編程語言中都是內建對象，包括 Python。迭代器抽象擁有兩個組成部分：一種獲取底層元素序列的下一個元素的機制，以及一種標識元素序列已經到達末尾，沒有更多剩餘元素的機制。在帶有內建對象系統的編程語言中，這個抽象通常相當於可以由類實現的特定接口。Python 的迭代器接口會在下一節中描述。

迭代器的實用性來源於一個事實，底層數據序列並不能顯式在內存中表達。迭代器提供了一種機制，可以依次計算序列中的每個值，但是所有元素不需要連續儲存。反之，當下個元素從迭代器獲取的時候，這個元素會按照請求計算，而不是從現有的內存來源中獲取。

範圍可以惰性計算序列中的元素，因為序列的表示是統一的，並且任何元素都可以輕易從範圍的起始和結束位置計算出來。迭代器支持更廣泛的底層有序數據集的惰性生成，因為它們不需要提供底層序列任意元素的訪問途徑。反之，它們僅僅需要按照順序，在每次其它元素被請求的時候，計算出序列的下一個元素。雖然不像序列可訪問任意元素那樣靈活（叫做隨機訪問），有序數據序列的順序訪問對於數據處理應用來說已經足夠了。

5.2.1 Python 迭代器

Python 迭代器接口包含兩個消息。__next__消息向迭代器獲取所表示的底層序列的下一個元素。為了對__next__方法調用做出回應，迭代器可以執行任何計算來獲取或計算底層數據序列的下一個元素。__next__的調用讓迭代器產生變化：它們向前移動迭代器的位置。所以多次調用__next__會有序返回底層序列的元素。在__next__的調用過程中，Python 通過StopIteration異常，來表示底層數據序列已經到達末尾。

下面的Letters類迭代了從a到d字母的底層序列。成員變量current儲存了序列中的當前字母。__next__方法返回這個字母，並且使用它來計算current的新值。

>>> class Letters(object):
        def __init__(self):
            self.current = 'a'
        def __next__(self):
            if self.current > 'd':
                raise StopIteration
            result = self.current
            self.current = chr(ord(result)+1)
            return result
        def __iter__(self):
            return self

__iter__消息是 Python 迭代器所需的第二個消息。它只是簡單返回迭代器，它對於提供迭代器和序列的通用接口很有用，在下一節會描述。

使用這個類，我們就可以訪問序列中的字母：

>>> letters = Letters()
>>> 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>
  File "<stdin>", line 12, in next
StopIteration

Letters示例只能迭代一次。一旦__next__()方法產生了StopIteration異常，它就從此之後一直這樣了。除非創建新的實例，否則沒有辦法來重置它。

迭代器也允許我們表示無限序列，通過實現永遠不會產生StopIteration異常的__next__方法。例如，下面展示的Positives類迭代了正整數的無限序列：

>>> class Positives(object):
        def __init__(self):
            self.current = 0;
        def __next__(self):
            result = self.current
            self.current += 1
            return result
        def __iter__(self):
            return self

5.2.2 for語句

Python 中，序列可以通過實現__iter__消息用於迭代。如果一個對象表示有序數據，它可以在for語句中用作可迭代對象，通過回應__iter__消息來返回迭代器。這個迭代器應擁有__next__()方法，依次返回序列中的每個元素，最後到達序列末尾時產生StopIteration異常。

>>> counts = [1, 2, 3]
>>> for item in counts:
        print(item)
1
2
3

在上面的實例中，counts列表返回了迭代器，作為__iter__()方法調用的回應。for語句之後反覆調用迭代器的__next__()方法，並且每次都將返回值賦給item。這個過程一直持續，直到迭代器產生了StopIteration異常，這時for語句就終止了。

使用我們關於迭代器的知識，我們可以拿while、賦值和try語句實現for語句的求值規則：

>>> i = counts.__iter__()
>>> try:
        while True:
            item = i.__next__()
            print(item)
    except StopIteration:
        pass
1
2
3

在上面，調用counts的__iter__方法所返回的迭代器綁定到了名稱i上面，便於依次獲取每個元素。StopIteration異常的處理子句不做任何事情，但是這個異常的處理提供了退出while循環的控制機制。

5.2.3 生成器和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

即使我們永不顯式定義__iter__()或__next__()方法，Python 會理解當我們使用yield語句時，我們打算定義生成器函數。調用時，生成器函數並不返回特定的產出值，而是返回一個生成器（一種迭代器），它自己就可以返回產出的值。生成器對象擁有__iter__和__next__方法，每個對__next__的調用都會從上次停留的地方繼續執行生成器函數，直到另一個yield語句執行的地方。

__next__第一次調用時，程序從letters_generator的函數體一直執行到進入yield語句。之後，它暫停並返回current值。yield語句並不破壞新創建的環境，而是為之後的使用保留了它。當__next__再次調用時，執行在它停留的地方恢復。letters_generator作用域中current和任何所綁定名稱的值都會在隨後的__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__()調用之前，生成器並不會開始執行任何生成器函數體中的語句。

5.2.4 可迭代對象

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__時返回了迭代器的新實例，那麼它就能被迭代多次。

新的可迭代類可以通過實現可迭代接口來定義。例如，下面的可迭代對象LetterIterable類在每次調用__iter__時返回新的迭代器來迭代字母。

>>> class LetterIterable(object):
        def __iter__(self):
            current = 'a'
            while current <= 'd':
                yield current
                current = chr(ord(current)+1)

__iter__方法是個生成器函數，它返回一個生成器對象，產出從'a'到'd'的字母。

Letters迭代器對象在單次迭代之後就被“用完”了，但是LetterIterable對象可被迭代多次。所以，LetterIterable示例可以用於all_pairs的參數。

>>> letters = LetterIterable()
>>> all_pairs(letters).__next__()
('a', 'a')

5.2.5 流

流提供了一種隱式表示有序數據的最終方式。流是惰性計算的遞歸列表。就像第三章的Rlist類那樣，Stream實例可以響應對其第一個元素和剩餘部分的獲取請求。同樣，Stream的剩餘部分還是Stream。然而不像RList，流的剩餘部分只在查找時被計算，而不是事先存儲。也就是說流的剩餘部分是惰性計算的。

為了完成這個惰性求值，流會儲存計算剩餘部分的函數。無論這個函數在什麼時候調用，它的返回值都作為流的一部分，儲存在叫做_rest的屬性中。下劃線表示它不應直接訪問。可訪問的屬性rest是個方法，它返回流的剩餘部分，並在必要時計算它。使用這個設計，流可以儲存計算剩餘部分的方式，而不用總是顯式儲存它們。

>>> class Stream(object):
        """A lazily computed recursive list."""
        def __init__(self, first, compute_rest, empty=False):
            self.first = first
            self._compute_rest = compute_rest
            self.empty = empty
            self._rest = None
            self._computed = False
        @property
        def rest(self):
            """Return the rest of the stream, computing it if necessary."""
            assert not self.empty, 'Empty streams have no rest.'
            if not self._computed:
                self._rest = self._compute_rest()
                self._computed = True
            return self._rest
        def __repr__(self):
            if self.empty:
                return '<empty stream>'
            return 'Stream({0}, <compute_rest>)'.format(repr(self.first))
>>> Stream.empty = Stream(None, None, True)

遞歸列表可使用嵌套表達式來定義。例如，我們可以創建RList，來表達1和5的序列，像下面這樣：

>>> r = Rlist(1, Rlist(2+3, Rlist.empty))

與之類似，我們可以創建一個Stream來表示相同序列。Stream在請求剩餘部分之前，並不會實際計算下一個元素5。

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

這裡，1是流的第一個元素，後面的lambda表達式是用於計算流的剩餘部分的函數。被計算的流的第二個元素又是一個返回空流的函數。

訪問遞歸列表r和流s中的元素擁有相似的過程。但是，5儲存在了r之中，而對於s來說，它在首次被請求時通過加法來按要求計算。

>>> r.first
1
>>> s.first
1
>>> r.rest.first
5
>>> s.rest.first
5
>>> r.rest
Rlist(5)
>>> s.rest
Stream(5, <compute_rest>)

雖然 r 的 rest 是一個單元素遞歸列表，但 s 的其餘部分包括一個計算其餘部分的函數；它將返回空流的事實可能還沒有被發現。

當構造一個 Stream 實例時，字段 self._computed 為 False ，表示 Stream 的 _rest 還沒有被計算。當通過點表達式請求 rest 屬性時，會調用 rest 方法，以 self._rest = self.compute_rest 觸發計算。由於 Stream 中的緩存機制，compute_rest 函數只被調用一次。

compute_rest 函數的基本屬性是它不接受任何參數，並返回一個 Stream。

惰性求值使我們能夠用流來表示無限的順序數據集。例如，我們可以從任意 first 開始表示遞增的整數。

>>> def make_integer_stream(first=1):
      def compute_rest():
        return make_integer_stream(first+1)
      return Stream(first, compute_rest)
>>> ints = make_integer_stream()
>>> ints
Stream(1, <compute_rest>)
>>> ints.first
1

當make_integer_stream首次被調用時，它返回了一個流，流的first是序列中第一個整數（默認為1）。但是，make_integer_stream實際是遞歸的，因為這個流的compute_rest以自增的參數再次調用了make_integer_stream。這會讓make_integer_stream變成遞歸的，同時也是惰性的。

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

無論何時請求整數流的rest，都僅僅遞歸調用make_integer_stream。

操作序列的相同高階函數 -- map和filter -- 同樣可應用於流，雖然它們的實現必須修改來惰性調用它們的參數函數。map_stream在一個流上映射函數，這會產生一個新的流。局部定義的compute_rest函數確保了無論什麼時候rest被計算出來，這個函數都會在流的剩餘部分上映射。

>>> def map_stream(fn, s):
        if s.empty:
            return s
        def compute_rest():
            return map_stream(fn, s.rest)
        return Stream(fn(s.first), compute_rest)

流可以通過定義compute_rest函數來過濾，這個函數在流的剩餘部分上調用過濾器函數。如果過濾器函數拒絕了流的第一個元素，剩餘部分會立即計算出來。因為filter_stream是遞歸的，剩餘部分可能會多次計算直到找到了有效的first元素。

>>> def filter_stream(fn, s):
        if s.empty:
            return s
        def compute_rest():
            return filter_stream(fn, s.rest)
        if fn(s.first):
            return Stream(s.first, compute_rest)
        return compute_rest()

map_stream和filter_stream展示了流式處理的常見模式：無論流的剩餘部分何時被計算，局部定義的compute_rest函數都會對流的剩餘部分遞歸調用某個處理函數。

為了觀察流的內容，我們需要將其截斷為有限長度，並轉換為 Python list。

>>> def truncate_stream(s, k):
        if s.empty or k == 0:
            return Stream.empty
        def compute_rest():
            return truncate_stream(s.rest, k-1)
        return Stream(s.first, compute_rest)
>>> def stream_to_list(s):
        r = []
        while not s.empty:
            r.append(s.first)
            s = s.rest
        return r

這些便利的函數允許我們驗證map_stream的實現，使用一個非常簡單的例子，從3到7的整數平方。

>>> s = make_integer_stream(3)
>>> s
Stream(3, <compute_rest>)
>>> m = map_stream(lambda x: x*x, s)
>>> m
Stream(9, <compute_rest>)
>>> stream_to_list(truncate_stream(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)

通過截斷primes流，我們可以枚舉素數的任意前綴：

>>> p1 = primes(make_integer_stream(2))
>>> stream_to_list(truncate_stream(p1, 7))
[2, 3, 5, 7, 11, 13, 17]

流和迭代器不同，因為它們可以多次傳遞給純函數，並且每次都產生相同的值。素數流並沒有在轉換為列表之後“用完”。也就是說，在將流的前綴轉換為列表之後，p1的第一個元素仍舊是2。

>>> p1.first
2

就像遞歸列表提供了序列抽象的簡單實現，流提供了簡單、函數式的遞歸數據結構，它通過高階函數的使用實現了惰性求值。