摘要：示例有理數(shù)的算術(shù)有理數(shù)可表示為整數(shù)的比值，并且它組成了實數(shù)的一個重要子類。有理數(shù)的值需要兩部分來描述。這里的重要概念是，通過將有理數(shù)表示為整數(shù)的比值，我們能夠完全避免近似問題。返回有理數(shù)的分子。

來源：2.2   Data Abstraction
譯者：飛龍
協(xié)議：CC BY-NC-SA 4.0

由于我們希望在程序中表達(dá)世界中的大量事物，我們發(fā)現(xiàn)它們的大多數(shù)都具有復(fù)合結(jié)構(gòu)。日期是年月日，地理位置是精度和緯度。為了表示位置，我們希望程序語言具有將精度和緯度“粘合”為一對數(shù)據(jù)的能力 -- 也就是一個復(fù)合數(shù)據(jù)結(jié)構(gòu) -- 使我們的程序能夠以一種方式操作數(shù)據(jù)，將位置看做單個概念單元，它擁有兩個部分。

復(fù)合數(shù)據(jù)的使用也讓我們增加程序的模塊性。如果我們可以直接將地理位置看做對象來操作，我們就可以將程序的各個部分分離，它們根據(jù)這些值如何表示來從本質(zhì)上處理這些值。將某個部分從程序中分離的一般技巧是一種叫做數(shù)據(jù)抽象的強(qiáng)大的設(shè)計方法論。這個部分用于處理數(shù)據(jù)表示，而程序用于操作數(shù)據(jù)。數(shù)據(jù)抽象使程序更易于設(shè)計、維護(hù)和修改。

數(shù)據(jù)抽象的特征類似于函數(shù)抽象。當(dāng)我們創(chuàng)建函數(shù)抽象時，函數(shù)如何實現(xiàn)的細(xì)節(jié)被隱藏了，而且特定的函數(shù)本身可以被任何具有相同行為的函數(shù)替換。換句話說，我們可以構(gòu)造抽象來使函數(shù)的使用方式和函數(shù)的實現(xiàn)細(xì)節(jié)分離。與之相似，數(shù)據(jù)抽象是一種方法論，使我們將復(fù)合數(shù)據(jù)對象的使用細(xì)節(jié)與它的構(gòu)造方式隔離。

數(shù)據(jù)抽象的基本概念是構(gòu)造操作抽象數(shù)據(jù)的程序。也就是說，我們的程序應(yīng)該以一種方式來使用數(shù)據(jù)，對數(shù)據(jù)做出盡可能少的假設(shè)。同時，需要定義具體的數(shù)據(jù)表示，獨立于使用數(shù)據(jù)的程序。我們系統(tǒng)中這兩部分的接口是一系列函數(shù)，叫做選擇器和構(gòu)造器，它們基于具體表示實現(xiàn)了抽象數(shù)據(jù)。為了演示這個技巧，我們需要考慮如何設(shè)計一系列函數(shù)來操作有理數(shù)。

當(dāng)你閱讀下一節(jié)時，要記住當(dāng)今編寫的多數(shù) Python 代碼使用了非常高級的抽象數(shù)據(jù)類型，它們內(nèi)建于語言中，比如類、字典和列表。由于我們正在了解這些抽象的工作原理，我們自己不能使用它們。所以，我們會編寫一些不那么 Python 化的代碼 -- 它并不是在語言中實現(xiàn)我們的概念的通常方式。但是，我們所編寫的代碼出于教育目的，它展示了這些抽象如何構(gòu)建。要記住計算機(jī)科學(xué)并不只是學(xué)習(xí)如何使用編程語言，也學(xué)習(xí)它們的工作原理。

有理數(shù)可表示為整數(shù)的比值，并且它組成了實數(shù)的一個重要子類。類似于1/3或者17/29的有理數(shù)通常可編寫為：

/

其中，和都是值為整數(shù)的占位符。有理數(shù)的值需要兩部分來描述。

有理數(shù)在計算機(jī)科學(xué)中很重要，因為它們就像整數(shù)那樣，可以準(zhǔn)確表示。無理數(shù)（比如pi 或者 e 或者 sqrt(2)）會使用有限的二元展開代替為近似值。所以在原則上，有理數(shù)的處理應(yīng)該讓我們避免算術(shù)中的近似誤差。

但是，一旦我們真正將分子與分母相除，我們就會只剩下截斷的小數(shù)近似值：

>>> 1/3
0.3333333333333333

當(dāng)我們開始執(zhí)行測試時，這個近似值的問題就會出現(xiàn)：

>>> 1/3 == 0.333333333333333300000  # Beware of approximations
True

計算機(jī)如何將實數(shù)近似為定長的小數(shù)擴(kuò)展，是另一門課的話題。這里的重要概念是，通過將有理數(shù)表示為整數(shù)的比值，我們能夠完全避免近似問題。所以出于精確，我們希望將分子和分母分離，但是將它們看做一個單元。

我們從函數(shù)抽象中了解到，我們可以在了解某些部分的實現(xiàn)之前開始編出東西來。讓我們一開始假設(shè)我們已經(jīng)擁有一種從分子和分母中構(gòu)造有理數(shù)的方式。我們也假設(shè)，給定一個有理數(shù)，我們都有辦法來提取（或選中）它的分子和分母。讓我們進(jìn)一步假設(shè)，構(gòu)造器和選擇器以下面三個函數(shù)來提供：

make_rat(n, d)返回分子為n和分母為d的有理數(shù)。

numer(x)返回有理數(shù)x的分子。

denom(x)返回有理數(shù)x的分母。

我們在這里正在使用一個強(qiáng)大的合成策略：心想事成。我們并沒有說有理數(shù)如何表示，或者numer、denom和make_rat如何實現(xiàn)。即使這樣，如果我們擁有了這三個函數(shù)，我們就可以執(zhí)行加法、乘法，以及測試有理數(shù)的相等性，通過調(diào)用它們：

>>> def add_rat(x, y):
        nx, dx = numer(x), denom(x)
        ny, dy = numer(y), denom(y)
        return make_rat(nx * dy + ny * dx, dx * dy)
>>> def mul_rat(x, y):
        return make_rat(numer(x) * numer(y), denom(x) * denom(y))
>>> def eq_rat(x, y):
        return numer(x) * denom(y) == numer(y) * denom(x)

現(xiàn)在我們擁有了由選擇器函數(shù)numer和denom，以及構(gòu)造器函數(shù)make_rat定義的有理數(shù)操作。但是我們還沒有定義這些函數(shù)。我們需要以某種方式來將分子和分母粘合為一個單元。

為了實現(xiàn)我們的數(shù)據(jù)抽象的具體層面，Python 提供了一種復(fù)合數(shù)據(jù)結(jié)構(gòu)叫做tuple，它可以由逗號分隔的值來構(gòu)造。雖然并不是嚴(yán)格要求，圓括號通常在元組周圍。

>>> (1, 2)
(1, 2)

元組的元素可以由兩種方式解構(gòu)。第一種是我們熟悉的多重賦值：

>>> pair = (1, 2)
>>> pair
(1, 2)
>>> x, y = pair
>>> x
1
>>> y
2

實際上，多重賦值的本質(zhì)是創(chuàng)建和解構(gòu)元組。

訪問元組元素的第二種方式是通過下標(biāo)運(yùn)算符，寫作方括號：

>>> pair[0]
1
>>> pair[1]
2

Python 中的元組（以及多數(shù)其它編程語言中的序列）下標(biāo)都以 0 開始，也就是說，下標(biāo) 0 表示第一個元素，下標(biāo) 1 表示第二個元素，以此類推。我們對這個下標(biāo)慣例的直覺是，下標(biāo)表示一個元素距離元組開頭有多遠(yuǎn)。

與元素選擇操作等價的函數(shù)叫做getitem，它也使用下標(biāo)以 0 開始的位置來在元組中選擇元素。

元素是原始類型，也就是說 Python 的內(nèi)建運(yùn)算符可以操作它們。我們不久之后再來看元素的完整特性。現(xiàn)在，我們只對元組如何作為膠水來實現(xiàn)抽象數(shù)據(jù)類型感興趣。

表示有理數(shù)。元素提供了一個自然的方式來將有理數(shù)實現(xiàn)為一對整數(shù)：分子和分母。我們可以通過操作二元組來實現(xiàn)我們的有理數(shù)構(gòu)造器和選擇器函數(shù)。

>>> def make_rat(n, d):
        return (n, d)
>>> def numer(x):
        return getitem(x, 0)
>>> def denom(x):
        return getitem(x, 1)

用于打印有理數(shù)的函數(shù)完成了我們對抽象數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)。

>>> def str_rat(x):
        """Return a string "n/d" for numerator n and denominator d."""
        return "{0}/{1}".format(numer(x), denom(x))

將它與我們之前定義的算術(shù)運(yùn)算放在一起，我們可以使用我們定義的函數(shù)來操作有理數(shù)了。

>>> half = make_rat(1, 2)
>>> str_rat(half)
"1/2"
>>> third = make_rat(1, 3)
>>> str_rat(mul_rat(half, third))
"1/6"
>>> str_rat(add_rat(third, third))
"6/9"

就像最后的例子所展示的那樣，我們的有理數(shù)實現(xiàn)并沒有將有理數(shù)化為最簡。我們可以通過修改make_rat來補(bǔ)救。如果我們擁有用于計算兩個整數(shù)的最大公約數(shù)的函數(shù)，我們可以在構(gòu)造一對整數(shù)之前將分子和分母化為最簡。這可以使用許多實用工具，例如 Python 庫中的現(xiàn)存函數(shù)。

>>> from fractions import gcd
>>> def make_rat(n, d):
        g = gcd(n, d)
        return (n//g, d//g)

雙斜杠運(yùn)算符//表示整數(shù)除法，它會向下取整除法結(jié)果的小數(shù)部分。由于我們知道g能整除n和d，整數(shù)除法正好適用于這里。現(xiàn)在我們的

>>> str_rat(add_rat(third, third))
"2/3"

符合要求。這個修改只通過修改構(gòu)造器來完成，并沒有修改任何實現(xiàn)實際算術(shù)運(yùn)算的函數(shù)。

擴(kuò)展閱讀。上面的str_rat實現(xiàn)使用了格式化字符串，它包含了值的占位符。如何使用格式化字符串和format方法的細(xì)節(jié)請見 Dive Into Python 3 的格式化字符串一節(jié)。

在以更多復(fù)合數(shù)據(jù)和數(shù)據(jù)抽象的例子繼續(xù)之前，讓我們思考一些由有理數(shù)示例產(chǎn)生的問題。我們使用構(gòu)造器make_rat和選擇器numer和denom定義了操作。通常，數(shù)據(jù)抽象的底層概念是，基于某個值的類型的操作如何表達(dá)，為這個值的類型確定一組基本的操作。之后使用這些操作來操作數(shù)據(jù)。

我們可以將有理數(shù)系統(tǒng)想象為一系列層級。

平行線表示隔離系統(tǒng)不同層級的界限。每一層上，界限分離了使用數(shù)據(jù)抽象的函數(shù)（上面）和實現(xiàn)數(shù)據(jù)抽象的函數(shù)（下面）。使用有理數(shù)的程序僅僅通過算術(shù)函數(shù)來操作它們：add_rat、mul_rat和eq_rat。相應(yīng)地，這些函數(shù)僅僅由構(gòu)造器和選擇器make_rat、numer和and denom來實現(xiàn)，它們本身由元組實現(xiàn)。元組如何實現(xiàn)的字節(jié)和其它層級沒有關(guān)系，只要元組支持選擇器和構(gòu)造器的實現(xiàn)。

每一層上，盒子中的函數(shù)強(qiáng)制劃分了抽象的邊界，因為它們僅僅依賴于上層的表現(xiàn)（通過使用）和底層的實現(xiàn)（通過定義）。這樣，抽象界限可以表現(xiàn)為一系列函數(shù)。

抽象界限具有許多好處。一個好處就是，它們使程序更易于維護(hù)和修改。很少的函數(shù)依賴于特定的表現(xiàn)，當(dāng)一個人希望修改表現(xiàn)時，不需要做很多修改。

我們通過實現(xiàn)算術(shù)運(yùn)算來開始實現(xiàn)有理數(shù)，實現(xiàn)為這三個非特定函數(shù)：make_rat、numer和denom。這里，我們可以認(rèn)為已經(jīng)定義了數(shù)據(jù)對象 -- 分子、分母和有理數(shù) -- 上的運(yùn)算，它們的行為由這三個函數(shù)規(guī)定。

但是數(shù)據(jù)意味著什么？我們還不能說“提供的選擇器和構(gòu)造器實現(xiàn)了任何東西”。我們需要保證這些函數(shù)一起規(guī)定了正確的行為。也就是說，如果我們從整數(shù)n和d中構(gòu)造了有理數(shù)x，那么numer(x)/denom(x)應(yīng)該等于n/d。

通常，我們可以將抽象數(shù)據(jù)類型當(dāng)做一些選擇器和構(gòu)造器的集合，并帶有一些行為條件。只要滿足了行為條件（比如上面的除法特性），這些函數(shù)就組成了數(shù)據(jù)類型的有效表示。

這個觀點可以用在其他數(shù)據(jù)類型上，例如我們?yōu)閷崿F(xiàn)有理數(shù)而使用的二元組。我們實際上不會談?wù)撛M是什么，而是談?wù)撚烧Z言提供的，用于操作和創(chuàng)建元組的運(yùn)算符。我們現(xiàn)在可以描述二元組的行為條件，二元組通常叫做偶對，在表示有理數(shù)的問題中有所涉及。

為了實現(xiàn)有理數(shù)，我們需要一種兩個整數(shù)的粘合形式，它具有下列行為：

如果一個偶對p由x和y構(gòu)造，那么getitem_pair(p, 0)返回x，getitem_pair(p, 1)返回y。

我們可以實現(xiàn)make_pair和getitem_pair，它們和元組一樣滿足這個描述：

>>> def make_pair(x, y):
        """Return a function that behaves like a pair."""
        def dispatch(m):
            if m == 0:
                return x
            elif m == 1:
                return y
        return dispatch
>>> def getitem_pair(p, i):
        """Return the element at index i of pair p."""
        return p(i)

使用這個實現(xiàn)，我們可以創(chuàng)建和操作偶對：

>>> p = make_pair(1, 2)
>>> getitem_pair(p, 0)
1
>>> getitem_pair(p, 1)
2

這個函數(shù)的用法不同于任何直觀上的，數(shù)據(jù)應(yīng)該是什么的概念。而且，這些函數(shù)滿足于在我們的程序中表示復(fù)合數(shù)據(jù)。

需要注意的微妙的一點是，由make_pair返回的值是叫做dispatch的函數(shù)，它接受參數(shù)m并返回x或y。之后，getitem_pair調(diào)用了這個函數(shù)來獲取合適的值。我們在這一章中會多次返回拆解這個函數(shù)的話題。

這個偶對的函數(shù)表示并不是 Python 實際的工作機(jī)制（元組實現(xiàn)得更直接，出于性能因素），但是它可以以這種方式工作。這個函數(shù)表示雖然不是很明顯，但是是一種足夠完美來表示偶對的方式，因為它滿足了偶對唯一需要滿足的條件。這個例子也表明，將函數(shù)當(dāng)做值來操作的能力，提供給我們表示復(fù)合數(shù)據(jù)的能力。