2.2 数据抽象

当我们考虑世界上我们想要在程序中表示的大量事物时，我们发现它们中的大多数都有复合结构。 例如，地理位置包含纬度和经度坐标。 为了表示位置，我们希望我们的编程语言能够将纬度和经度结合在一起形成一对，这是一个复合数据值，我们的程序可以将其作为单个概念单元进行操作，但它也有两个可以单独考虑的部分。

复合数据的使用使我们能够增加程序的模块化。 如果我们可以将地理位置作为整体值来操作，那么我们就可以将程序中使用位置计算的部分从这些位置如何表示的细节中屏蔽掉。 将处理数据如何表示的程序部分与处理数据如何操作的程序部分隔离开来的通用技术是一种强大的设计方法论，称为数据抽象。 数据抽象使程序更容易设计、维护和修改。

数据抽象在性质上与功能抽象相似。 当我们创建一个函数抽象时，函数如何实现的细节可以被抑制，并且特定的函数本身可以被具有相同总体行为的任何其他函数所替代。 换句话说，我们可以进行抽象，将函数的使用方式与函数如何实现的细节分离开来。 类似地，数据抽象将如何使用复合数据值与如何构造复合数据值的细节分离开来。

数据抽象的基本思想是对程序进行结构化，以便它们能够对抽象数据进行操作。 也就是说，我们的程序应该以这样一种方式使用数据，即尽可能少地对数据做出假设。 同时，一个具体的数据表示被定义为程序的独立部分。

程序的这两个部分，操作抽象数据的部分和定义具体表示的部分，由一组根据具体表示实现抽象数据的函数连接起来。 为了说明这种技术，我们将考虑如何设计一组用于处理有理数的函数。

2.2.1 示例:有理数

有理数是整数的比率，有理数是实数的一个重要子类。有理数，如1/3或17/29通常写成：

<numerator>/<denominator>

<分子>和<分母>都是整数值的占位符。这两部分都需要准确地描述有理数的值。实际上，整数的除法会产生一个浮点近似值，从而失去整数的精确精度。

>>> 1/3
0.3333333333333333
>>> 1/3 == 0.333333333333333300000  # Dividing integers yields an approximation
True

然而，我们可以通过结合分子和分母来创建有理数的精确表示。

通过使用函数抽象，我们知道，在实现程序的某些部分之前，我们可以开始高效地编程。 让我们先假设我们已经有了一种从分子和分母构造有理数的方法。 我们还假设，给定一个有理数，我们有一种选择其分子和分母成分的方法。 让我们进一步假设构造函数和选择器可以使用以下三个函数：

1. rational(n, d)返回分子n、分母d的有理数。

2. number (x)返回有理数x的分子。

3. denom(x)返回有理数x的分母。

我们在这里使用的是一个设计程序的强大策略：一厢情愿。我们还没有阐述一个有理数是如何表示的，或者numer, denom, rational函数是如何实现的。即便如此，如果我们确实定义了这三个函数，我们就可以进行加法、乘法、打印和测试有理数是否相等：

>>> def add_rationals(x, y):
        nx, dx = numer(x), denom(x)
        ny, dy = numer(y), denom(y)
        return rational(nx * dy + ny * dx, dx * dy)

>>> def mul_rationals(x, y):
        return rational(numer(x) * numer(y), denom(x) * denom(y))

>>> def print_rational(x):
        print(numer(x), '/', denom(x))

>>> def rationals_are_equal(x, y):
        return numer(x) * denom(y) == numer(y) * denom(x)

现在，我们已经根据选择器函数number和denom以及构造器函数rational定义了有理数的操作，但我们还没有定义这些函数。我们需要的是一种把分子和分母结合成复合值的方法。

2.2.2 对

为了使我们能够实现数据抽象的具体级别，Python提供了一个称为列表的复合结构，可以通过将表达式放在用逗号分隔的方括号中来构造。这样的表达式称为列表字面量。

>>> pair = [10, 20]
>>> pair
[10, 20]
>>> x, y = pair
>>> x
10
>>> y
20

访问列表中元素的第二种方法是通过元素选择操作符，也使用方括号表示。与列表文字不同，直接跟在另一个表达式后面的方括号表达式并不求值为列表值，而是从前一个表达式的值中选择元素。

>>> pair[0]
10
>>> pair[1]
20

Python中的列表(以及大多数其他编程语言中的序列)是0索引的，这意味着索引0选择第一个元素，索引1选择第二个元素，以此类推。支持这种索引约定的一种直观感觉是，索引表示元素从列表开始的偏移量。

元素选择操作符的等效函数称为getitem，它还使用0索引位置从列表中选择元素。

>>> from operator import getitem
>>> getitem(pair, 0)
10
>>> getitem(pair, 1)
20

在Python中，双元素列表并不是表示对的唯一方法。将两个值捆绑成一个值的任何方式都可以被认为是一对。列表是一种常见的方法。列表也可以包含两个以上的元素，我们将在本章后面讨论。

表示有理数。我们现在可以用一对整数表示一个有理数：一个分子和一个分母。

>>> def rational(n, d):
        return [n, d]

>>> def numer(x):
        return x[0]

>>> def denom(x):
        return x[1]

再加上我们前面定义的算术运算，我们可以用我们定义的函数来处理有理数。

>>> half = rational(1, 2)
>>> print_rational(half)
1 / 2
>>> third = rational(1, 3)
>>> print_rational(mul_rationals(half, third))
1 / 6
>>> print_rational(add_rationals(third, third))
6 / 9

如上例所示，我们的有理数实现不会将有理数减少到最低项。我们可以通过改变rational的实现来弥补这个缺陷。如果我们有一个计算两个整数的最大公分母的函数，我们可以使用它在构造对之前将分子和分母降为最低项。与许多有用的工具一样，这样的函数已经存在于Python库中。

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

层除法运算符，//表示整数除法，它将除法结果的小数部分舍入。因为我们知道g能将n和d都整除，所以在这种情况下整数除法是正确的。这个修改过的rational实现确保了用最低的术语表达rational。

>>> print_rational(add_rationals(third, third))
2 / 3

这种改进是通过改变构造函数而不改变任何实现实际算术操作的函数来实现的。

2.2.3 抽象的障碍

在继续讨论复合数据和数据抽象的更多示例之前，让我们考虑一下有理数示例所提出的一些问题。 我们用构造函数rational和选择器number和denom来定义操作。 一般来说，数据抽象的基本思想是识别一组基本的操作，根据这些操作，某种类型的值的所有操作都将被表示出来，然后在操作数据时只使用这些操作。 通过以这种方式限制操作的使用，在不改变程序行为的情况下更容易改变抽象数据的表示。

对于有理数，程序的不同部分使用不同的运算操作有理数，如下表所述。

程序的部分是…	把理性当...	单独利用......
使用有理数进行计算	整个数据值	add_rational, mul_rational, rationals_are_equal, print_rational
创建rational或实现rational操作	分子和分母	rational, numer, denom
为有理函数实现选择器和构造函数	双元素列表	列表文字和元素选择

在上面的每一层中，最后一列中的函数强制了一个抽象障碍。这些函数由较高的级别调用，并使用较低的抽象级别实现。

当程序的某个部分可以使用较高级别的函数而不是使用较低级别的函数时，就会发生抽象障碍冲突。例如，一个计算有理数平方的函数最好使用mul_rational来实现，它不假设任何关于有理数实现的事情。

>>> def square_rational(x):
        return mul_rational(x, x)

直接引用分子和分母会违反一个抽象障碍。

>>> def square_rational_violating_once(x):
        return rational(numer(x) * numer(x), denom(x) * denom(x))

假设用两元素列表来表示有理数会违反两个抽象障碍。

>>> def square_rational_violating_twice(x):
        return [x[0] * x[0], x[1] * x[1]]

抽象障碍使程序更容易维护和修改。 依赖于特定表示的函数越少，当人们想要改变这种表示时，所需要的更改就越少。 square_rational的所有这些实现都有正确的行为，但只有第一个实现对未来的更改是健壮的。 即使我们改变了有理数的表示形式，square_rational函数也不需要更新。 相比之下，square_rational_violating_once在选择器或构造器签名发生更改时需要更改，而square_rational_violating_twice在有理数的实现发生更改时需要更新。

2.2.4 数据属性

抽象障碍塑造了我们思考数据的方式。 有理数的有效表示不受任何特定实现的限制(如双元素列表); 它是一个由rational返回的值，可以传递给number和denom。 此外，构造函数和选择器之间必须保持适当的关系。 也就是说，如果我们从整数n和d构造一个有理数x，那么number (x)/denom(x)等于n/d。

一般来说，我们可以使用选择器和构造器的集合，以及一些行为条件来表达抽象数据。 只要满足行为条件(如上面的分割属性)，选择器和构造器就构成了一种数据的有效表示。 抽象障碍下面的实现细节可能会改变，但如果行为没有改变，那么数据抽象仍然有效，使用该数据抽象编写的任何程序都将保持正确。

这个观点可以广泛地应用，包括我们用来实现有理数的对值。 实际上，我们从未详细说明什么是pair，只是说该语言提供了创建和操作带有两个元素的列表的方法。 我们需要实现pair的行为是将两个值粘合在一起。 作为一种行为条件，

• 如果由值x和y构造一对p，则select(p, 0)返回x, select(p, 1)返回y。

我们实际上并不需要list类型来创建pair。相反，我们可以实现两个函数pair和select来满足这个描述，就像实现一个两个元素的列表一样。

>>> def pair(x, y):
        """Return a function that represents a pair."""
        def get(index):
            if index == 0:
                return x
            elif index == 1:
                return y
        return get

>>> def select(p, i):
        """Return the element at index i of pair p."""
        return p(i)

通过这个实现，我们可以创建和操作对。

>>> p = pair(20, 14)
>>> select(p, 0)
20
>>> select(p, 1)
14

这种高阶函数的使用与我们对数据应该是什么的直观概念完全不同。 然而，这些函数足以在程序中表示对。 函数足以表示复合数据。

展示pair的函数表示的意义并不在于Python实际上是这样工作的(出于效率原因，列表实现得更直接)，而是它可以这样工作。 函数表示虽然晦涩，但却是表示成对的一种完全合适的方式，因为它满足成对需要满足的唯一条件。 数据抽象的实践使我们能够轻松地在表示之间切换。