摘要：序列不是特定的抽象數據類型，而是不同類型共有的一組行為。不像抽象數據類型，我們并沒有闡述如何構造序列。這兩個選擇器和一個構造器，以及一個常量共同實現了抽象數據類型的遞歸列表。

來源：2.3   Sequences
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0

序列是數據值的順序容器。不像偶對只有兩個元素，序列可以擁有任意（但是有限）個有序元素。

序列在計算機科學中是強大而基本的抽象。例如，如果我們使用序列，我們就可以列出伯克利的每個學生，或者世界上的每所大學，或者每所大學中的每個學生。我們可以列出上過的每一門課，提交的每個作業(yè)，或者得到的每個成績。序列抽象讓數千個數據驅動的程序影響著我們每天的生活。

序列不是特定的抽象數據類型，而是不同類型共有的一組行為。也就是說，它們是許多序列種類，但是都有一定的屬性。特別地，

長度。序列擁有有限的長度。

元素選擇。序列的每個元素都擁有相應的非負整數作為下標，它小于序列長度，以第一個元素的 0 開始。

不像抽象數據類型，我們并沒有闡述如何構造序列。序列抽象是一組行為，它們并沒有完全指定類型（例如，使用構造器和選擇器），但是可以在多種類型中共享。序列提供了一個抽象層級，將特定程序如何操作序列類型的細節(jié)隱藏。

這一節(jié)中，我們開發(fā)了一個特定的抽象數據類型，它可以實現序列抽象。我們之后介紹實現相同抽象的 Python 內建類型。

對于有理數，我們使用二元組將兩個整數對象配對，之后展示了我們可以同樣通過函數來實現偶對。這種情況下，每個我們構造的偶對的元素都是整數。然而，就像表達式，元組可以嵌套。每個偶對的元素本身也可以是偶對，這個特性在實現偶對的任意一個方法，元組或調度函數中都有效。

可視化偶對的一個標準方法 -- 這里也就是偶對(1,2) -- 叫做盒子和指針記號。每個值，復合或原始，都描述為指向盒子的指針。原始值的盒子只包含那個值的表示。例如，數值的盒子只包含數字。偶對的盒子實際上是兩個盒子：左邊的部分（箭頭指向的）包含偶對的第一個元素，右邊的部分包含第二個。

嵌套元素的 Python 表達式：

>>> ((1, 2), (3, 4))
((1, 2), (3, 4))

具有下面的結構：

使用元組作為其它元組元素的能力，提供了我們編程語言中的一個新的組合手段。我們將這種將元組以這種方式嵌套的能力叫做元組數據類型的封閉性。通常，如果組合結果自己可以使用相同的方式組合，組合數據值的方式就滿足封閉性。封閉性在任何組合手段中都是核心能力，因為它允許我們創(chuàng)建層次數據結構 -- 結構由多個部分組成，它們自己也由多個部分組成，以此類推。我們在第三章會探索一些層次結構?，F在，我們考慮一個特定的重要結構。

我們可以使用嵌套偶對來構建任意長度的元素列表，它讓我們能夠實現抽象序列。下面的圖展示了四元素列表1, 2, 3, 4的遞歸表示：

這個列表由一系列偶對表示。每個偶對的第一個元素是列表中的元素，而第二個元素是用于表示列表其余部分的偶對。最后一個偶對的第二個元素是None，它表明列表到末尾了。我們可以使用嵌套的元組字面值來構造這個結構：

>>> (1, (2, (3, (4, None))))
(1, (2, (3, (4, None))))

這個嵌套的結構通常對應了一種非常實用的序列思考方式，我們在 Python 解釋器的執(zhí)行規(guī)則中已經見過它了。一個非空序列可以劃分為：

它的第一個元素，以及

序列的其余部分。

序列的其余部分本身就是一個（可能為空的）序列。我們將序列的這種看法叫做遞歸，因為序列包含其它序列作為第二個組成部分。

由于我們的列表表示是遞歸的，我們在實現中叫它rlist，以便不會和 Python 內建的list類型混淆，我們會稍后在這一章介紹它。一個遞歸列表可以由第一個元素和列表的剩余部分構造。None值表示空的遞歸列表。

>>> empty_rlist = None
>>> def make_rlist(first, rest):
        """Make a recursive list from its first element and the rest."""
        return (first, rest)
>>> def first(s):
        """Return the first element of a recursive list s."""
        return s[0]
>>> def rest(s):
        """Return the rest of the elements of a recursive list s."""
        return s[1]

這兩個選擇器和一個構造器，以及一個常量共同實現了抽象數據類型的遞歸列表。遞歸列表唯一的行為條件是，就像偶對那樣，它的構造器和選擇器是相反的函數。

如果一個遞歸列表s由元素f和列表r構造，那么first(s)返回f，并且rest(s)返回r。

我們可以使用構造器和選擇器來操作遞歸列表。

>>> counts = make_rlist(1, make_rlist(2, make_rlist(3, make_rlist(4, empty_rlist))))
>>> first(counts)
1
>>> rest(counts)
(2, (3, (4, None)))

遞歸列表可以按序儲存元素序列，但是它還沒有實現序列的抽象。使用我們已經定義的數據類型抽象，我們就可以實現描述兩個序列的行為：長度和元素選擇。

>>> def len_rlist(s):
        """Return the length of recursive list s."""
        length = 0
        while s != empty_rlist:
            s, length = rest(s), length + 1
        return length
>>> def getitem_rlist(s, i):
        """Return the element at index i of recursive list s."""
        while i > 0:
            s, i = rest(s), i - 1
        return first(s)

現在，我們可以將遞歸列表用作序列了：

>>> len_rlist(counts)
4
>>> getitem_rlist(counts, 1)  # The second item has index 1
2

兩個實現都是可迭代的。它們隔離了嵌套偶對的每個層級，直到列表的末尾（在len_rlist中），或者到達了想要的元素（在getitem_rlist中）。

下面的一系列環(huán)境圖示展示了迭代過程，getitem_rlist通過它找到了遞歸列表中下標1中的元素2。

while頭部中的表達式求值為真，這會導致while語句組中的賦值語句被執(zhí)行：

這里，局部名稱s現在指向以原列表第二個元素開始的子列表?，F在，while頭中的表達式求值為假，于是 Python 會求出getitem_rlist最后一行中返回語句中的表達式。

最后的環(huán)境圖示展示了調用first的局部幀，它包含綁定到相同子列表的s。first函數挑選出值2并返回了它，完成了getitem_rlist的調用。

這個例子演示了遞歸列表計算的常見模式，其中迭代的每一步都操作原列表的一個逐漸變短的后綴。尋找遞歸列表的長度和元素的漸進式處理過程需要一些時間來計算。（第三章中，我們會學會描述這種函數的計算時間。）Python 的內建序列類型以不同方式實現，它對于計算序列長度和獲取元素并不具有大量的計算開銷。

實際上，我們引入用于形成原始偶對的tuple類型本身就是完整的序列類型。元組比起我們以函數式實現的偶對抽象數據結構，本質上提供了更多功能。

元組具有任意的長度，并且也擁有序列抽象的兩個基本行為：長度和元素選擇。下面的digits是一個四元素元組。

>>> digits = (1, 8, 2, 8)
>>> len(digits)
4
>>> digits[3]
8

此外，元素可以彼此相加以及與整數相乘。對于元組，加法和乘法操作并不對元素相加或相乘，而是組合和重復元組本身。也就是說，operator模塊中的add函數（以及+運算符）返回兩個被加參數連接成的新元組。operator模塊中的mul函數（以及*運算符）接受整數k和元組，并返回含有元組參數k個副本的新元組。

>>> (2, 7) + digits * 2
(2, 7, 1, 8, 2, 8, 1, 8, 2, 8)

映射。將一個元組變換為另一個元組的強大手段是在每個元素上調用函數，并收集結果。這一計算的常用形式叫做在序列上映射函數，對應內建函數map。map的結果是一個本身不是序列的對象，但是可以通過調用tuple來轉換為序列。它是元組的構造器。

>>> alternates = (-1, 2, -3, 4, -5)
>>> tuple(map(abs, alternates))
(1, 2, 3, 4, 5)

map函數非常重要，因為它依賴于序列抽象：我們不需要關心底層元組的結構，只需要能夠獨立訪問每個元素，以便將它作為參數傳入用于映射的函數中（這里是abs）。

映射本身就是通用計算模式的一個實例：在序列中迭代所有元素。為了在序列上映射函數，我們不僅僅需要選擇特定的元素，還要依次選擇每個元素。這個模式非常普遍，Python 擁有額外的控制語句來處理序列數據：for語句。

考慮一個問題，計算一個值在序列中出現了多少次。我們可以使用while循環(huán)實現一個函數來計算這個數量。

>>> def count(s, value):
        """Count the number of occurrences of value in sequence s."""
        total, index = 0, 0
        while index < len(s):
            if s[index] == value:
                total = total + 1
            index = index + 1
        return total
>>> count(digits, 8)
2

Python for語句可以通過直接迭代元素值來簡化這個函數體，完全不需要引入index。例如（原文是For example，為雙關語），我們可以寫成：

>>> def count(s, value):
        """Count the number of occurrences of value in sequence s."""
        total = 0
        for elem in s:
            if elem == value:
                total = total + 1
        return total
>>> count(digits, 8)
2

for語句按照以下過程來執(zhí)行：

求出頭部表達式，它必須產生一個可迭代的值。

對于序列中的每個元素值，按順序：

在局部環(huán)境中將變量名綁定到這個值上。

執(zhí)行語句組。

步驟 1 引用了可迭代的值。序列是可迭代的，它們的元素可看做迭代的順序。Python 的確擁有其他可迭代類型，但是我們現在只關注序列。術語“可迭代對象”的一般定義會在第四章的迭代器一節(jié)中出現。

這個求值過程的一個重要結果是，在for語句執(zhí)行完畢之后，會綁定到序列的最后一個元素上。這個for循環(huán)引入了另一種方式，其中局部環(huán)境可以由語句來更新。

序列解構。程序中的一個常見模式是，序列的元素本身就是序列，但是具有固定的長度。for語句可在頭部中包含多個名稱，將每個元素序列“解構”為各個元素。例如，我們擁有一個偶對（也就是二元組）的序列：

>>> pairs = ((1, 2), (2, 2), (2, 3), (4, 4))

下面的for語句的頭部帶有兩個名詞，會將每個名稱x和y分別綁定到每個偶對的第一個和第二個元素上。

>>> for x, y in pairs:
        if x == y:
            same_count = same_count + 1
>>> same_count
2

這個綁定多個名稱到定長序列中多個值的模式，叫做序列解構。它的模式和我們在賦值語句中看到的，將多個名稱綁定到多個值的模式相同。

范圍。range是另一種 Python 的內建序列類型，它表示一個整數范圍。范圍可以使用range函數來創(chuàng)建，它接受兩個整數參數：所得范圍的第一個數值和最后一個數值加一。

>>> range(1, 10)  # Includes 1, but not 10
range(1, 10)

在范圍上調用tuple構造器會創(chuàng)建與范圍具有相同元素的元組，使元素易于查看。

>>> tuple(range(5, 8))
(5, 6, 7)

如果只提供了一個元素，它會解釋為最后一個數值加一，范圍開始于 0。

>>> total = 0
>>> for k in range(5, 8):
        total = total + k
>>> total
18

常見的慣例是將單下劃線字符用于for頭部，如果這個名稱在語句組中不會使用。

>>> for _ in range(3):
        print("Go Bears!")

Go Bears!
Go Bears!
Go Bears!

要注意對解釋器來說，下劃線只是另一個名稱，但是在程序員中具有固定含義，它表明這個名稱不應出現在任何表達式中。

我們已經介紹了兩種原生數據類型，它們實現了序列抽象：元組和范圍。兩個都滿足這一章開始時的條件：長度和元素選擇。Python 還包含了兩種序列類型的行為，它們擴展了序列抽象。

成員性。可以測試一個值在序列中的成員性。Python 擁有兩個操作符in和not in，取決于元素是否在序列中出現而求值為True和False。

>>> digits
(1, 8, 2, 8)
>>> 2 in digits
True
>>> 1828 not in digits
True

所有序列都有叫做index和count的方法，它會返回序列中某個值的下標（或者數量）。

切片。序列包含其中的子序列。我們在開發(fā)我們的嵌套偶對實現時觀察到了這一點，它將序列切分為它的第一個元素和其余部分。序列的切片是原序列的任何部分，由一對整數指定。就像range構造器那樣，第一個整數表示切片的起始下標，第二個表示結束下標加一。

Python 中，序列切片的表示類似于元素選擇，使用方括號。冒號分割了起始和結束下標。任何邊界上的省略都被當作極限值：起始下標為 0，結束下標是序列長度。

>>> digits[0:2]
(1, 8)
>>> digits[1:]
(8, 2, 8)

Python 序列抽象的這些額外行為的枚舉，給我們了一個機會來反思數據抽象通常由什么構成。抽象的豐富性（也就是說它包含行為的多少）非常重要。對于使用抽象的用戶，額外的行為很有幫助，另一方面，滿足新類型抽象的豐富需求是個挑戰(zhàn)。為了確保我們的遞歸列表實現支持這些額外的行為，需要一些工作量。另一個抽象豐富性的負面結果是，它們需要用戶長時間學習。

序列擁有豐富的抽象，因為它們在計算中無處不在，所以學習一些復雜的行為是合理的。通常，多數用戶定義的抽象應該盡可能簡單。

擴展閱讀。切片符號接受很多特殊情況，例如負的起始值，結束值和步長。Dive Into Python 3 中有一節(jié)叫做列表切片，完整描述了它。這一章中，我們只會用到上面描述的基本特性。

文本值可能比數值對計算機科學來說更基本。作為一個例子，Python 程序以文本編寫和儲存。Python 中原生的文本數據類型叫做字符串，相應的構造器是str。

關于字符串在 Python 中如何表示和操作有許多細節(jié)。字符串是豐富抽象的另一個示例，程序員需要滿足一些實質性要求來掌握。這一節(jié)是字符串基本行為的摘要。

字符串字面值可以表達任意文本，被單引號或者雙引號包圍。

>>> "I am string!"
"I am string!"
>>> "I"ve got an apostrophe"
"I"ve got an apostrophe"
>>> "您好"
"您好"

我們已經在代碼中見過字符串了，在print的調用中作為文檔字符串，以及在assert語句中作為錯誤信息。

字符串滿足兩個基本的序列條件，我們在這一節(jié)開始介紹過它們：它們擁有長度并且支持元素選擇。

>>> city = "Berkeley"
>>> len(city)
8
>>> city[3]
"k"

字符串的元素本身就是包含單一字符的字符串。字符是字母表中的任意單一字符，標點符號，或者其它符號。不像許多其它編程語言那樣，Python 沒有多帶帶的字符類型，任何文本都是字符串，表示單一字符的字符串長度為 1、

就像元組，字符串可以通過加法和乘法來組合：

>>> city = "Berkeley"
>>> len(city)
8
>>> city[3]
"k"

字符串的行為不同于 Python 中其它序列類型。字符串抽象沒有實現我們?yōu)樵M和范圍描述的完整序列抽象。特別地，字符串上實現了成員性運算符in，但是與序列上的實現具有完全不同的行為。它匹配子字符串而不是元素。

>>> "here" in "Where"s Waldo?"
True

與之相似，字符串上的count和index方法接受子串作為參數，而不是單一字符。count的行為有細微差別，它統(tǒng)計字符串中非重疊字串的出現次數。

>>> "Mississippi".count("i")
4
>>> "Mississippi".count("issi")
1

多行文本。字符串并不限制于單行文本，三個引號分隔的字符串字面值可以跨越多行。我們已經在文檔字符串中使用了三個引號。

>>> """The Zen of Python
claims, Readability counts.
Read more: import this."""
"The Zen of Python
claims, "Readability counts."
Read more: import this."

在上面的打印結果中， （叫做“反斜杠加 n”）是表示新行的單一元素。雖然它表示為兩個字符（反斜杠和 n）。它在長度和元素選擇上被認為是單個字符。

字符串強制。字符串可以從 Python 的任何對象通過以某個對象值作為參數調用str構造函數來創(chuàng)建，這個字符串的特性對于從多種類型的對象中構造描述性字符串非常實用。

>>> str(2) + " is an element of " + str(digits)
"2 is an element of (1, 8, 2, 8)"

str函數可以以任何類型的參數調用，并返回合適的值，這個機制是后面的泛用函數的主題。

方法。字符串在 Python 中的行為非常具有生產力，因為大量的方法都返回字符串的變體或者搜索其內容。一部分這些方法由下面的示例介紹。

>>> "1234".isnumeric()
True
>>> "rOBERT dE nIRO".swapcase()
"Robert De Niro"
>>> "snakeyes".upper().endswith("YES")
True

擴展閱讀。計算機中的文本編碼是個復雜的話題。這一章中，我們會移走字符串如何表示的細節(jié)，但是，對許多應用來說，字符串如何由計算機編碼的特定細節(jié)是必要的知識。Dive Into Python 3 的 4.1 ~ 4.3 節(jié)提供了字符編碼和 Unicode 的描述。

在復合數據的處理中，我們強調了數據抽象如何讓我們設計程序而不陷入數據表示的細節(jié)，以及抽象如何為我們保留靈活性來嘗試備用表示。這一節(jié)中，我們引入了另一種強大的設計原則來處理數據結構 -- 接口約定的用法。

接口約定使在許多組件模塊中共享的數據格式，它可以混合和匹配來展示數據。例如，如果我們擁有多個函數，它們全部接受序列作為參數并且返回序列值，我們就可以把它們每一個用于上一個的輸出上，并選擇任意一種順序。這樣，我們就可以通過將函數鏈接成流水線，來創(chuàng)建一個復雜的過程，每個函數都是簡單而專一的。

這一節(jié)有兩個目的，來介紹以接口約定組織程序的概念，以及展示模塊化序列處理的示例。

考慮下面兩個問題，它們首次出現，并且只和序列的使用相關。

對前n個斐波那契數中的偶數求和。

列出一個名稱中的所有縮寫字母，它包含每個大寫單詞的首字母。

這些問題是有關系的，因為它們可以解構為簡單的操作，它們接受序列作為輸入，并產出序列作為輸出。而且，這些操作是序列上的計算的一般方法的實例。讓我們思考第一個問題，它可以解構為下面的步驟：

 enumerate     map    filter  accumulate
-----------    ---    ------  ----------
naturals(n)    fib    iseven     sum

下面的fib函數計算了斐波那契數（現在使用了for語句更新了第一章中的定義）。

>>> def fib(k):
        """Compute the kth Fibonacci number."""
        prev, curr = 1, 0  # curr is the first Fibonacci number.
        for _ in range(k - 1):
             prev, curr = curr, prev + curr
        return curr

謂詞iseven可以使用整數取余運算符%來定義。

>>> def iseven(n):
        return n % 2 == 0

map和filter函數是序列操作，我們已經見過了map，它在序列中的每個元素上調用函數并且收集結果。filter函數接受序列，并且返回序列中謂詞為真的元素。兩個函數都返回間接對象，map和filter對象，它們是可以轉換為元組或求和的可迭代對象。

>>> nums = (5, 6, -7, -8, 9)
>>> tuple(filter(iseven, nums))
(6, -8)
>>> sum(map(abs, nums))
35

現在我們可以實現even_fib，第一個問題的解，使用map、filter和sum。

>>> def sum_even_fibs(n):
        """Sum the first n even Fibonacci numbers."""
        return sum(filter(iseven, map(fib, range(1, n+1))))
>>> sum_even_fibs(20)
3382

現在，讓我們思考第二個問題。它可以解構為序列操作的流水線，包含map和filter。

enumerate  filter   map   accumulate
---------  ------  -----  ----------
  words    iscap   first    tuple

字符串中的單詞可以通過字符串對象上的split方法來枚舉，默認以空格分割。

>>> tuple("Spaces between words".split())
("Spaces", "between", "words")

單詞的第一個字母可以使用選擇運算符來獲取，確定一個單詞是否大寫的謂詞可以使用內建謂詞isupper定義。

>>> def first(s):
        return s[0]
>>> def iscap(s):
        return len(s) > 0 and s[0].isupper()

這里，我們的縮寫函數可以使用map和filter定義。

>>> def acronym(name):
        """Return a tuple of the letters that form the acronym for name."""
        return tuple(map(first, filter(iscap, name.split())))
>>> acronym("University of California Berkeley Undergraduate Graphics Group")
("U", "C", "B", "U", "G", "G")

這些不同問題的相似解法展示了如何使用通用的計算模式，例如映射、過濾和累計，來組合序列的接口約定上的操作。序列抽象讓我們編寫出這些簡明的解法。

將程序表達為序列操作有助于我們設計模塊化的程序。也就是說，我們的設計由組合相關的獨立片段構建，每個片段都對序列進行轉換。通常，我們可以通過提供帶有接口約定的標準組件庫來鼓勵模塊化設計，接口約定以靈活的方式連接這些組件。

生成器表達式。Python 語言包含第二個處理序列的途徑，叫做生成器表達式。它提供了與map和reduce相似的功能，但是需要更少的函數定義。

生成器表達式組合了過濾和映射的概念，并集成于單一的表達式中，以下面的形式：

為了求出生成器表達式，Python 先求出，它必須返回一個可迭代值。之后，對于每個元素，按順序將元素值綁定到，求出過濾器表達式，如果它產生真值，就會求出映射表達式。

生成器表達式的求解結果值本身是個可迭代值。累計函數，比如tuple、sum、max和min可以將返回的對象作為參數。

>>> def acronym(name):
        return tuple(w[0] for w in name.split() if iscap(w))
>>> def sum_even_fibs(n):
        return sum(fib(k) for k in range(1, n+1) if fib(k) % 2 == 0)

生成器表達式是使用可迭代（例如序列）接口約定的特化語法。這些表達式包含了map和filter的大部分功能，但是避免了被調用函數的實際創(chuàng)建（或者，順便也避免了環(huán)境幀的創(chuàng)建需要調用這些函數）。

歸約。在我們的示例中，我們使用特定的函數來累計結果，例如tuple或者sum。函數式編程語言（包括 Python）包含通用的高階累加器，具有多種名稱。Python 在functools模塊中包含reduce，它對序列中的元素從左到右依次調用二元函數，將序列歸約為一個值。下面的表達式計算了五個因數的積。

>>> from operator import mul
>>> from functools import reduce
>>> reduce(mul, (1, 2, 3, 4, 5))
120

使用這個更普遍的累計形式，除了求和之外，我們也可以計算斐波那契數列中奇數的積，將序列用作接口約定。

>>> def product_even_fibs(n):
        """Return the product of the first n even Fibonacci numbers, except 0."""
        return reduce(mul, filter(iseven, map(fib, range(2, n+1))))
>>> product_even_fibs(20)
123476336640

與map、filter和reduce對應的高階過程的組合會再一次在第四章出現，在我們思考多臺計算機之間的分布式計算方法的時候。