Chapter 2 - Building Abstractions with Data

0 写在前面

2026/07/16
短学期结束，最近有些急躁了，不想落后时代，又感觉学习vibe coding等有种无力的感觉，迷茫了一会儿，昨天出去逛了逛，第一次去到杭州的工联CC和湖滨88，感受到了很好的氛围

还是不要死磕吧，cs61a的学习还是比较渐进的，先同步学着cs61a，其他的继续慢慢来吧

就这样吧，It’s MyGo!!!!!

1 Introduction

We concentrated in Chapter 1 on computational processes and on the role of functions in program design. We saw how to use primitive data (numbers) and primitive operations (arithmetic), how to form compound functions through composition and control, and how to create functional abstractions by giving names to processes.

We also saw that higher-order functions enhance the power of our language by enabling us to manipulate, and thereby to reason, in terms of general methods of computation. This is much of the essence(本质) of programming.

This chapter focuses on data. The techniques we investigate here will allow us to represent and manipulate information about many different domains.

1.1 Native Data Types

Every value in Python has a class that determines what type of value it is. Values that share a class also share behavior. For example, the integers 1 and 2 are both instances of the int class. These two values can be treated similarly.
The built-in type function allows us to inspect the class of any value.

>>> type(1.2)
<class 'float'>
>>> type('h')
<class 'str'>
>>> type('hello')
<class 'str'>
>>> type("hello")
<class 'str'>
>>> type(2)
<class 'int'>
>>> type(1+1j)
<class 'complex'>

目前我们使用的值都属于Python内置的少数几种原生数据类型(native data types)，原生数据类型有下列特性

1. 存在能直接求值(evaluate)为原生类型值的表达式，称为字面量(literals)，也就是说可以直接在代码中写出一个值

123       # 整数字面量（连续数字组成的序列）
3.14      # 浮点数
"hello"  # 字符串
True      # 布尔值

2. 存在用于操作原生类型值的内置函数和运算符

Python有三种原生数字类型，int, float, complex，即整数、实数、复数

int对象精确地表示整数，在内存允许的情况下没有大小限制，而float对象虽然能表示很大范围内的小数，但不是所有小数都能被精确表示，而且有最大值和最小值范围的限制，float值应视为实数的近似值

>>> 7/3*3
7.0
>>> 1/3*7*3
6.999999999999999

Although int values are combined above, dividing one int by another yields a float value: a truncated(截断的) finite approximation(有限近似) to the actual ratio of the two integers divided.(即得到的是对实际结果进行截断的近似值)

>>> 1/3
0.3333333333333333
>>> 1/3 == 0.33333333333333339
False
>>> 1/3 == 0.333333333333333339
True
>>> 1/3 == 0.333333333333333312345
True # 右边的数太长了，出现近似误差

Non-numeric types. Values can represent many other types of data, such as sounds, images, locations, web addresses, network connections, and more. A few are represented by native data types, such as the bool class for values True and False. The type for most values must be defined by programmers using the means of combination and abstraction that we will develop in this chapter.

2 Data Abstraction

As we consider the wide set of things in the world that we would like to represent in our programs, we find that most of them have compound structure.

For example, a geographic position has latitude and longitude coordinates. To represent positions, we would like our programming language to have the capacity to couple together a latitude and longitude to form a pair, a compound data value that our programs can manipulate as a single conceptual unit, but which also has two parts that can be considered individually.

复合数据的使用能提升我们程序的模块化程度，如果我们将地理位置作为一个整体值，我们可以将程序中使用地理位置进行计算的部分和地理位置如何表示的细节隔离开来，这种将程序中数据如何被表示和数据如何被操作隔离开来的设计方法论，称为数据抽象

The general technique of isolating the parts of a program that deal with how data are represented from the parts that deal with how data are manipulated is a powerful design methodology called data abstraction. Data abstraction makes programs much easier to design, maintain, and modify.

数据抽象和函数抽象很相似，我们创造函数抽象时，函数具体如何实现我们不关心，一个特定的函数可以被其他函数替换，只要它们的功能一样，换句话说，我们创建了这样一个抽象，它隔离开来函数被使用的方式和函数如何实现，即我们使用函数时不用关心它如何被实现。相似地，数据抽象隔离了一个复合数据如何被使用和复合数据如何被构造表示，即我们操作一个复合数据时不用关心它如何被表示，只把它当作数据就行。
这听起来很抽象，后面的例子会有所解释

The basic idea of data abstraction is to structure programs so that they operate on abstract data. That is, our programs should use data in such a way as to make as few assumptions about the data as possible.

写代码处理数据时，不要管数据底层结构长什么样，把它当作一个“黑盒”去使用，不要预先假定数据是用list还是什么其他数据结构存储的，只用它的“逻辑身份”去操作

At the same time, a concrete data representation is defined as an independent part of the program.

数据具体是怎么表示/存储/构造的，要作为单独的部分，比如主要代码里不要碰这些底层细节，尽量调用下面说的如同黑盒一般的函数

These two parts of a program, the part that operates on abstract data and the part that defines a concrete representation, are connected by a small set of functions that implement abstract data in terms of the concrete representation.
使用专门的函数作为连接数据如何表示和数据如何使用的桥梁/接口，主要的逻辑代码中只调用这些函数，不直接操作底层的结构

上面这些话也许很抽象，但其实是data abstraction的精髓，可以结合下面的例子去理解体会

2.1 Example

我们就以有理数作为例子
通过函数抽象，我们可以得到启发，开始编程前，我们完全可以假设我们已经有了一些特定功能的函数供我们使用，之后再去实现它们

我们先假设我们已经有了这么三个函数

rational(n, d) # returns the rational number with numerator n and denominator d

numer(x) # returns the numerator of the rational number x

denom(x) # returns the denominator of the rational number x

We are using here a powerful strategy for designing program: wishful thinking. We haven’t yet said how a rational number is represented, or how the functions numer, denom, and rational should be implemented. Even so, if we did define these three functions, we could then add, multiply, print, and test equality of rational numbers:

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

def mul_rational(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)

Now we have the operations on rational numbers defined in terms of the selector functions numer and denom, and the constructor function rational, but we haven’t yet defined these functions. What we need is some way to glue together a numerator and a denominator into a compound value.

2.2 Pairs

To enable us to implement the concrete level of our data abstraction, Python provides a compound structure called a list, which can be constructed by placing expressions within square brackets separated by commas. Such an expression is called a list literal.

>>> [10, 20]
[10, 20]

The elements of a list can be accessed in two ways. The first way is via our familiar method of multiple assignment, which unpacks a list into its elements and binds each element to a different name.

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

A second method for accessing the elements in a list is by the element selection operator.

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

Lists in Python (and sequences in most other programming languages) are 0-indexed.

The equivalent function for the element selection operator is called getitem.

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

Two-element lists are not the only method of representing pairs in Python. Any way of bundling two values together into one can be considered a pair. Lists are a common method to do so.

下面我们就使用a pair of two integers来表示有理数

def rational(n, d):
    """Construct a rational number that represent n/d"""
    return [n, d]

def numer(x):
    """Get the numerator of x"""
    return x[0]

def denom(x):
    """Get the denominator of x"""
    return x[1]

>>> print_rational(add_rational(third, half))
5 / 6
>>> print_rational(add_rational(third, third))
6 / 9

我们发现，不能实现约分。
这时就体现出数据抽象的强大之处，我们只需要改rational这一个函数，就能实现约分。
从后面的barrier也能看出，我们想在计算有理数时能实现约分，并不是每个函数都需要单独重写，由于这一层（创造有理数以及实现对有理数的操作）我们只使用rational、numer和denom函数，只需要改它们就行了

from math import gcd
def rational(n, d):
    g = gcd(n, d)
    return [n//g, d//g]

"""
This improvement was accomplished by changing the constructor without changing 
any of the functions that implement the actual arithmetic operations.
"""

Rational 是一种抽象数据类型，它定义了分数的运算接口。在这个 Python 具体实现里，底层数据表示用的是列表 (list) 来存放分子分母。同时封装了约分、加法等操作函数。如果抛开语言，从物理存储来看，这个列表底层是基于连续内存的（动态）数组结构。

2.3 Abstraction Barriers

在有理数的例子中，我们依据构造函数rational和选择函数numer和denom来定义各种操作

数据抽象的思想就是确定一组基本操作，通过这些操作来表达对某类数值的所有处理行为，而且在处理数据时只使用这些操作，像这样限制操作的使用，我们更容易修改抽象数据的底层表示而不影响其他（层）

对于有理数，程序的不同部分使用不同的基本操作处理有理数，由此构成了不同的层，层与层之间有着抽象屏障(abstraction barrier)

In each layer above, the functions in the final column enforce an abstraction barrier. These functions are called by a higher level and implemented using a lower level of abstraction.

An abstraction barrier violation occurs whenever a part of the program that can use a higher level function instead uses a function in a lower level.

例如一个计算有理数的平方的函数，我们应该使用mul_rational

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


"""
Referring directly to numerators and denominators would violate one abstraction barrier.
"""
def square_rational_violating_once(x):
    return rational(numer(x) * numer(x), denom(x) * denom(x))

"""
Assuming that rationals are represented as two-element lists would violate two abstraction barriers.
"""
def square_rational_violating_twice(x):
    return [x[0] * x[0], x[1] * x[1]]

抽象屏障使程序更容易维护和修改，依赖于特定数据表示的函数越少，当我们想改变这种表示时需要修改的地方就越少，上述平方函数中，第一种更加健壮，即便我们改变有理数的表示方式，square_rational也不需要改变，而如果选择函数或构造函数的signature改变，square_rational_violating_once就需要改变（当然，mul_rational那些最顶层的基本操作函数也要变），而只要有理数的底层实现改变了，square_rational_violating_twice就要改变

2.4 The Properties of Data

A valid representation of a rational number is not restricted to any particular implementation (such as a two-element list); it is a value returned by rational that can be passed to numer, and denom. In addition, the appropriate relationship must hold among the constructor and selectors. That is, if we construct a rational number x from integers n and d, then it should be the case that numer(x)/denom(x) is equal to n/d.

In general, we can express abstract data using a collection of selectors and constructors, together with some behavior conditions. As long as the behavior conditions are met (比如一个x，它的分子是n分母是d，那么numer(x)/denom(x)应该等于n/d；比如2/3乘1/3应该得到2/9等), the selectors and constructors constitute a valid representation of a kind of data.

The implementation details below an abstraction barrier may change, but if the behavior does not, then the data abstraction remains valid, and any program written using this data abstraction will remain correct.

下面我们用第三层来说明上面的理论。我们用于实现有理数的pair，pair到底是啥？我们也不知道，只是Python语言提供了创建和处理两个元素的list的方法，我们对于pair，只要求它把两个值放到一起，且可以分别获得它的两个值这个行为(behavior)，只要满足了这个behavior condition就可以，即

If a pair p was constructed from values x and y, then select(p, 0) returns x, and select(p, 1) returns y.

我们完全可以

def rational(n, d):
    """Return a function that represents a pair"""
    def select(name):
        if name == 'n':
            return n
        elif name == 'd':
            return d
    return select
    
def numer(x):
    return x('n')
def denom(x):
    return x('d')

这里修改的是上图的第三层(即如何构造有理数和创建选择器)，这时我们把有理数视作两个元素的pair，之前的rational返回一个pair性质的[n, d]，而现在的rational返回一个pair性质的函数select，即可以通过selector (numer和denom) 获得它的两个元素

如你所见，我们用函数表示了复合数据，这和我们对于数据应该是怎么样的直觉有些不符，但函数的确足够表示复合数据，正如上面，函数表示了pair

实际上，Python中使用list表示pair是更直接且高效的，但是用函数表示pair是一种完全适当的方式，因为它满足了所有pair需要满足的条件

3 Sequences

A sequence is an ordered collection of values. The sequence is a powerful, fundamental abstraction in computer science. Sequences are not instances of a particular built-in type or abstract data representation, but instead a collection of behaviors that are shared among several different types of data.

序列有很多种，但它们有共同的行为

• Length. 一个序列有有限的长度，空的序列长度为0
• Element Selection. 序列可以用下标选取元素

Python包含多种属于序列的原生数据类型，其中最重要的是list
为什么序列不是数据抽象？明明只关注行为？我不知道

3.1 Lists

数据类型可以简单理解为数据对象+对数据的相应操作，在编程语言层面，算是语言给变量的“标签”，规定了这个变量在语法层面能干什么、占多少字节。
抽象数据类型是一种数据类型，它只说明数据对象集和操作集是什么，至于数据怎么表示，操作怎么实现不管。
数据结构是计算机中存储、组织数据的方式，包括逻辑结构（如表、树、图），也包括物理存储结构（是否连续，数组还是链表）

在Python语言层面，list是一种内置的数据类型，list是一种数据结构，逻辑上有一列数据，是个线性表，底层是基于连续内存的动态数组

弄清这些我也不知道是否有必要分清的概念，蛮多哭赛……大概是给面试搞怕了也可能是自己确实连这些都不懂……

A list value is a sequence that can have arbitrary length.

>>> digits = [1, 8, 2, 8]
>>> len(digits) # len function returns the length of a sequence
4
>>> digits[3]
8
>>> digits[-1]
8 # -1是反向索引，倒过来数第1个
>>> digits * 2
[1, 8, 2, 8, 1, 8, 2, 8]
>>> [2, 7] + digits * 2
[2, 7, 1, 8, 2, 8, 1, 8, 2, 8]
# 加法就是合并，乘法是重复

Any values can be included in a list, including another list. Element selection can be applied multiple times in order to select a deeply nested element in a list containing lists.

>>> pairs = [[10, 20], [30, 40]]
>>> pairs[0]
[10, 20]
>>> pairs[0][1]
20

3.2 Sequence Iteration

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

# 使用for语句
def count(s, value):
    total = 0
    for elem in s:
        if elem == value:
            total = total + 1
    return total

for <name> in <expression>:
    <suite>

A for statement is executed by the following procedure:

1. Evaluate the header <expression>, which must yield(产生) an iterable value.
2. For each element value in that iterable value, in order:
   • Bind <name> to that value in the current frame.
   • Execute the <suite>.

in is a built-in operators for testing whether an element appears in a compound value.

>>> digits = [1,8,2,8]
>>> 1 in digits
True
>>> 5 in digits
False
>>> '1' in digits
False
>>> [1,8] in digits
False
>>> not(5 in digits)
True

这个执行过程提到了iterable value(可迭代值)
Lists are a type of sequence, and sequences are iterable values. Their elements are considered in their sequential order.

3.2.1 Sequence Unpacking

A common pattern in programs is to have a sequence of elements that are themselves sequences, but all of a fixed length. A for statement may include multiple names in its header to “unpack” each element sequence into its respective elements.

>>> pairs = [[1, 2], [2, 2], [4, 4]]
>>> same_count = 0
>>> for x, y in pairs:
...     if x == y:
...             same_count = same_count + 1
...
>>> same_count
2

This pattern of binding multiple names to multiple values in a fixed-length sequence is called sequence unpacking.

3.2.2 Ranges

A range is another built-in type of sequence in Python, which represents a range of integers. Ranges are created with range, which takes two integer arguments: the first number and one beyond the last number in the desired range.

>>> range(1, 10)
range(1, 10)

>>> list(range(1, 10))
[1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> list(range(4))
[0, 1, 2, 3]

Calling the list constructor(list这个类的构造函数) on a range evaluates to a list with the same elements as the range, so that the elements can be easily inspected.

Ranges commonly appear as the expression in a for header to specify the number of times that the suite should be executed: A common convention is to use a single underscore character for the name in the for header if the name is unused in the suite.

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

This underscore is just another name in the environment as far as the interpreter is concerned, but has a conventional meaning among programmers that indicates the name will not appear in any future expressions.

3.3 Sequence Processing

3.3.1 List Comprehensions

Many sequence processing operations can be expressed by evaluating a fixed expression for each element in a sequence and collecting the resulting values in a result sequence. In Python, a list comprehension is an expression that performs such a computation.

>>> odds = [1, 3, 5]
>>> [x+1 for x in odds]
[2, 4, 6]

The for keyword above is not part of a for statement, but instead part of a list comprehension because it is contained within square brackets. The sub-expression x+1 is evaluated with x bound to each element of odds in turn, and the resulting values are collected into a list.

Another common sequence processing operation is to select a subset of values that satisfy some condition. List comprehensions can also express this pattern, for instance selecting all elements of odds that evenly divide 25.

>>> [x for x in odds if 25 % x == 0]
[1, 5]

The general form of a list comprehension is:
[<map expression> for <name> in <sequence expression> if <filter expression>]

To evaluate a list comprehension, Python evaluates the <sequence expression>, which must return an iterable value. Then, for each element in order, the element value is bound to <name>, the filter expression is evaluated, and if it yields a true value, the map expression is evaluated. The values of the map expression are collected into a list.

def divisors(n):
    return [1] + [x for x in range(2, n) if n % x == 0]

3.3.2 Aggregation

A third common pattern in sequence processing is to aggregate all values in a sequence into a single value. The built-in functions sum, min, and max are all examples of aggregation(聚合) functions.

>>> sum([1, 2, 3])
6
>>> list = [1, 2, 3, 4, 5]
>>> min(list)
1
>>> max(range(5))
4

3.3.3 Higher-Order Functions

The common patterns we have observed in sequence processing can be expressed using higher-order functions.

def apply_to_all(map_fn, s):
    """ 
    Evaluating an expression for each element in a sequence can be
    expressed by applying a function to each element. 
    """
    return [map_fn(x) for x in s]

def keep_if(filter_fn, s):
    """
    Selecting only elements for which some expression is true can be
    expressed by applying a function to each element.
    """
    return [x for x in s if filter_fn(x)]

def reduce(reduce_fn, s, initial):
    """
    Many forms of aggregation can be expressed as repeatedly applying a
    two-argument function to the reduced value so far and each element in turn.
    """
    reduced = initial
    for x in s:
        reduced = reduce_fn(reduced, x)
    return reduced

def sum_by_reduce(s):
    return reduce(add, s, 0)

3.3.4 Conventional Names

In the computer science community, the more common name for apply_to_all is map and the more common name for keep_if is filter. In Python, the built-in map and filter are generalizations of these functions that do not return lists. These functions are discussed in Chapter 4. The definitions above are equivalent to applying the list constructor to the result of built-in map and filter calls.

>>> apply_to_all = lambda map_fn, s: list(map(map_fn, s))

The reduce function is built into the functools module of the Python standard library. In this version, the initial argument is optional.

3.4 Sequence Abstraction

We have introduced two native data types that satisfy the sequence abstraction: lists and ranges. Both satisfy the conditions with which we began this section: length and element selection. Python includes two more behaviors of sequence types that extend the sequence abstraction.

3.4.1 Membership

A value can be tested for membership in a sequence. Python has two operators in and not in that evaluate to True or False depending on whether an element appears in a sequence.

3.4.2 Slicing

>>> odds = [3,5,7,9,11]
>>> list(range(1,3))
[1, 2]
>>> [odds[i] for i in range(1,3)]
[5, 7]
>>> odds[1:3]
[5, 7] # 第1个和第2个
>>> odds[:3] # 默认从0开始
[3, 5, 7]
>>> odds[1:] # 默认到最后一个下标+1结束
[5, 7, 9, 11]
>>> odds[:]
[3, 5, 7, 9, 11]

Enumerating(列举) these additional behaviors of the Python sequence abstraction gives us an opportunity to reflect upon what constitutes(构成) a useful data abstraction in general. The richness of an abstraction (that is, how many behaviors it includes) has consequences. For users of an abstraction, additional behaviors can be helpful. On the other hand, satisfying the requirements of a rich abstraction with a new data type can be challenging. Another negative consequence of rich abstractions is that they take longer for users to learn.

3.5 Strings

Text values are perhaps more fundamental to computer science than even numbers. As a case in point, Python programs are written and stored as text. The native data type for text in Python is called a string, and corresponds to the constructor str.

Strings are another example of a rich abstraction.

String literals can express arbitrary text, surrounded by either single or double quotation marks.

Strings satisfy the two basic conditions of a sequence that we introduced at the beginning of this section: they have a length and they support element selection.
Strings are sequences.

>>> 'hello'
'hello'
>>> "hello"
'hello'

>>> city = 'Hangzhou'
>>> len(city)
8
>>> city[3]
'g'

The elements of a string are themselves strings that have only a single character. A character is any single letter of the alphabet, punctuation mark, or other symbol. Unlike many other programming languages, Python does not have a separate character type; any text is a string, and strings that represent single characters have a length of 1.

>>> city + ', Zhejiang'
'Hangzhou, Zhejiang'
>>> city * 2
'HangzhouHangzhou'

The membership operator in applies to strings, but has an entirely different behavior than when it is applied to sequences. It matches substrings rather than elements.

>>> 'gzh' in city
True
>>> 'lo w' in 'hello world'
True

Strings aren’t limited to a single line. Triple quotes delimit string literals that span multiple lines.

>>> """Welcome
... hello
...     goodbye"""
'Welcome\nhello\n\tgoodbye'

String Coercion(字符串强制转换).
A string can be created from any object in Python by calling the str constructor function with an object value as its argument. This feature of strings is useful for constructing descriptive strings from objects of various types.

>>> '[1' in str([1, 2])
True

>>> str(2) + ' is an element of ' + str([1, 2, 5, 6])
'2 is an element of [1, 2, 5, 6]'

# String Slicing
>>> a = 'strap'
>>> a[0]
's'
>>> a[1:]
'trap'
>>> a[2:]
'rap'
>>> a[1:][1:]
'rap'

3.6 Trees

Our ability to use lists as the elements of other lists provides a new means of combination in our programming language. This ability is called a closure property(闭包) of a data type. In general, a method for combining data values has a closure property if the result of combination can itself be combined using the same method. Closure is the key to power in any means of combination because it permits us to create hierarchical structures — structures made up of parts, which themselves are made up of parts, and so on.

We can visualize lists in environment diagrams using box-and-pointer notation. A list is depicted as adjacent boxes that contain the elements of the list. Primitive values such as numbers, strings, boolean values, and None appear within an element box. Composite(复合的，混成的) values, such as function values and other lists, are indicated by an arrow.