\(2.2\)数据抽象

1.数据抽象的概念

  将数据分开表示为如何表示数据的部分\(constructor\)与如何操作数据的部分\(operator\)的方法被称为数据抽象。

  数据抽象在概念上与函数抽象类似。当我们创建函数抽象时，函数实现的细节可以被抑制，特定函数本身可以被具有相同整体行为的任何其他函数替换。换句话说，我们可以制作一个抽象，将函数的使用方式与函数的实现细节分开。而数据抽象也将对复合数据的处理方式与对复合数据的构造方式分离开来。

  数据抽象的基本思想是组织程序，使它们能够在抽象的数据上运行。也就是说，我们的程序使用数据的方式应该尽可能少地对数据进行假设(即基本的操作步骤尽可能少)。同时将具体的数据表示定义为程序的一个独立部分。

  程序操作抽象数据的部分和定义数据表示的部分，由一小组函数连接起来，这些函数根据具体表示实现抽象数据。下举一例说明数据抽象流程的实现。

2.实例讲解——对有理数操作的实现：

  有理数的定义是两个整数的和。由于计算机的浮点数计算会降低运算精度，我们通过分数实现有理数的表示与运算。

  \(a.\)通过假设实现\(operator\)

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

• ration(n,d)：返回\(n\over d\)表示的有理数
• numer(x)：返回\(x\)的分子
• denom(x)：返回\(x\)的分母

  在这里我们用到了程序设计的重要思想：\(wishful\;thinking\)。我们并不知道这三个函数具体如何实现，但我们假设它们已经实现了，于是就可以通过假设实现加、减、乘、除等基本操作：

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)
#这是未约分后的，约分后结果除以gcd即可

  现在我们实现了基于\(selector\)变量与\(constructor\)变量的\(operator\)函数，剩下的任务就是具体实现我们的假设。

  \(b.\)\(selector\)与\(constructor\)的实现

  我们利用\(python\)自带的\(list\)功能实现\(pair\)的构建：

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

3.抽象屏障

  一般来说，数据抽象的基本思想是确定一组基本的操作，以此来表示对某种值的所有操作，然后只使用这些操作来操作数据。通过以这种方式限制操作的使用，更容易在不改变程序行为的情况下改变抽象数据的表示。对有理数的基本操作如下：

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

  例如，实现有理数的平方和应如下书写：

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

  抽象屏障使程序更容易维护和修改。依赖于特定表示形式的函数越少，想要更改该表示形式时所需的更改就越少。按照如上方式定义的平方和函数，在维护和修改时只需要调整\(mul\)函数即可。

4.数据的属性

  一般来说，我们可以使用一组选择器\(selector\)和构造函数\(constructor\)以及一些行为条件\(operator\)来表示抽象数据。只要满足行为条件(如上面的除法属性) ，选择器和构造器就构成了一种数据的有效表示。抽象屏障之下的实现细节可能会改变，但如果行为没有改变，那么抽象化仍然有效，并且使用这个抽象化编写的任何程序都将保持正确。

  例如上述对有理数的操作，我们并没有说明什么是\(pair\)，只是说该数据提供了用两个元素创建和操作列表的方法。我们需要实现一对的行为是将两个值粘合在一起，并且能够分别调用两值中的任意一个。我们也可以用如下函数实现这个操作：

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

  由此可以看出，我们对数据的抽象化有很多种表示方式，我们可以在多种表达方式中自由切换。