第二章 构造数据抽象
导读
在第一章中，我们学习了如何通过过程抽象来构造程序，将复杂的计算分解为可管理的小部分。然而，真实的计算问题往往涉及复杂的数据对象——不仅仅是数字和布尔值，还包括字符串、列表、树、图等结构化数据。如何表示和操作这些复杂的数据？如何在数据表示之上建立抽象，使得程序可以独立于数据的具体表示？这正是本章要解决的核心问题。
第二章"构造数据抽象"将介绍 Scheme 提供的数据构造机制，特别是 cons 对（pair）以及由此构建的各种数据结构。我们将学习数据抽象的原则——如何将数据的使用与数据的表示分离，使得程序更加模块化和可维护。我们还将探讨符号数据处理、序列操作、层次结构等主题，最终理解数据作为过程的深刻含义。
本章的学习目标包括：
- 理解数据抽象的概念和实现方法
- 掌握 pair 和 list 的构造与操作
- 学会使用序列操作（map、filter、accumulate）处理数据
- 理解层次数据结构的遍历与操作
- 掌握符号数据的表示与处理
- 理解数据作为过程的观点
- 了解通用型操作和数据导向编程
核心概念详解
2.1 数据抽象的基本思想
数据抽象（data abstraction）是将数据的使用方式与数据的表示方式分离的技术。它的核心思想是：定义数据对象时，我们只关心数据"能做什么"（即可以对其执行哪些操作），而不关心数据"是什么"（即数据在计算机中如何存储）。
以有理数为例。有理数可以表示为两个整数的比值 p/q。我们可以定义一组操作：
make-rat：构造有理数numer：提取分子denom：提取分母add-rat、sub-rat、mul-rat、div-rat：有理数运算
这些操作构成了有理数的抽象接口。只要接口保持不变，我们可以自由修改有理数的内部表示，而不影响使用有理数的程序。
(define (add-rat x y)
(make-rat (+ (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(define (sub-rat x y)
(make-rat (- (* (numer x) (denom y))
(* (numer y) (denom x)))
(* (denom x) (denom y))))
(define (mul-rat x y)
(make-rat (* (numer x) (numer y))
(* (denom x) (denom y))))
(define (div-rat x y)
(make-rat (* (numer x) (denom y))
(* (denom x) (numer y))))
(define (equal-rat? x y)
(= (* (numer x) (denom y))
(* (numer y) (denom x))))这些过程只依赖于抽象接口，不依赖于具体实现。这就是数据抽象的力量。
2.2 Pair 与 List
Scheme 提供了一对一的数据构造机制——cons，以及对应的选择器——car 和 cdr。
(define x (cons 1 2))
(car x) ; 返回 1
(cdr x) ; 返回 2cons 将两个值组合成一个 pair（对），car 提取 pair 的第一个元素，cdr 提取 pair 的第二个元素。pair 是 Scheme 中最基本的数据构造单元。
通过将 pair 的元素本身也设为 pair，我们可以构建更复杂的数据结构。列表（list）是最常用的复合数据结构：
(define list1 (cons 1 (cons 2 (cons 3 (cons 4 nil)))))
; 等价于
(define list1 (list 1 2 3 4))列表是一系列 pair 的链式结构，最后一个 pair 的 cdr 指向空表 nil（或写作 '()）。这种结构称为proper list（正规列表）。
列表的基本操作：
cons：在列表头部添加元素car：获取列表的第一个元素cdr：获取列表的剩余部分null?：判断列表是否为空list-ref：获取列表的第 n 个元素length：计算列表长度append：连接两个列表
(define (list-ref items n)
(if (= n 0)
(car items)
(list-ref (cdr items) (- n 1))))
(define (length items)
(if (null? items)
0
(+ 1 (length (cdr items)))))
(define (append list1 list2)
(if (null? list1)
list2
(cons (car list1) (append (cdr list1) list2))))2.3 序列操作
列表作为序列，可以使用一组通用的操作模式来处理。这些模式是函数式编程的核心技术。
map：对序列中的每个元素应用一个过程，返回结果序列。
(define (map proc items)
(if (null? items)
nil
(cons (proc (car items))
(map proc (cdr items)))))
; 使用示例
(map (lambda (x) (* x x)) (list 1 2 3 4))
; 返回 (1 4 9 16)map 将过程应用于序列的每个元素，是一种非常重要的抽象。它隐藏了遍历序列的细节，使得我们可以专注于对单个元素的处理逻辑。
filter：根据谓词筛选序列中的元素。
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
; 使用示例
(filter odd? (list 1 2 3 4 5))
; 返回 (1 3 5)accumulate（也称为 fold 或 reduce）：将序列的元素通过二元操作累积起来。
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
; 使用示例
(accumulate + 0 (list 1 2 3 4 5))
; 返回 15
(accumulate * 1 (list 1 2 3 4 5))
; 返回 120这三个操作可以组合使用，实现复杂的数据处理任务。例如，计算序列中所有偶数的平方和：
(define (sum-of-squares-of-even seq)
(accumulate + 0
(map (lambda (x) (* x x))
(filter even? seq))))这种编程风格称为管道式编程（pipeline programming），数据像流水线一样通过一系列操作，每个操作对数据进行转换或筛选。
2.4 层次数据结构
列表的元素本身也可以是列表，形成层次数据结构（hierarchical data structure）。树是最常见的层次结构。
(define tree (list (list 1 2) (list 3 4) (list 5 6)))处理树结构的基本方法是递归。树的每个节点可以看作是一个子树，递归地处理每个子树，然后将结果组合。
(define (count-leaves tree)
(cond ((null? tree) 0)
((not (pair? tree)) 1)
(else (+ (count-leaves (car tree))
(count-leaves (cdr tree))))))映射树（tree mapping）是对树中每个叶子节点应用一个过程：
(define (map-tree proc tree)
(cond ((null? tree) nil)
((not (pair? tree)) (proc tree))
(else (cons (map-tree proc (car tree))
(map-tree proc (cdr tree))))))另一个重要的树操作是深反向（deep reverse）：
(define (deep-reverse items)
(cond ((null? items) nil)
((not (pair? items)) items)
(else (append (deep-reverse (cdr items))
(list (deep-reverse (car items)))))))2.5 符号数据
到目前为止，我们处理的数据都是数字和结构。Scheme 还允许我们处理符号（symbol），即名称本身。
使用引号（quote）可以将符号与变量的值区分开：
(define a 1)
a ; 返回 1
'a ; 返回符号 a符号数据在构建解释器、处理代数表达式等场景中非常重要。
符号列表（list of symbols）是常见的数据形式：
(define symbols '(a b c d))成员检测：
(define (memq item x)
(cond ((null? x) #f)
((eq? item (car x)) x)
(else (memq item (cdr x)))))eq? 用于判断两个符号是否相同（即是否是同一个符号对象），equal? 用于判断两个结构是否相同（包括数字、字符串等的值比较）。
2.6 示例：符号微分
符号微分是符号数据处理的一个经典应用。我们可以定义一组规则来计算代数表达式的导数：
(define (deriv exp var)
(cond ((number? exp) 0)
((variable? exp)
(if (same-variable? exp var) 1 0))
((sum? exp)
(make-sum (deriv (addend exp) var)
(deriv (augend exp) var)))
((product? exp)
(make-sum
(make-product (multiplier exp)
(deriv (multiplicand exp) var))
(make-product (deriv (multiplier exp) var)
(multiplicand exp))))
(else (error "unknown expression type -- DERIV" exp))))这里我们使用选择器（addend、augend、multiplier、multiplicand）和构造器（make-sum、make-product）来操作代数表达式。这些过程构成了符号微分的抽象接口。
表达式的表示可以是列表，例如 (+ x y) 表示 x + y，(* x y) 表示 x * y。选择器和构造器的实现依赖于这种表示：
(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (sum? x) (and (pair? x) (eq? (car x) '+)))
(define (addend s) (cadr s))
(define (augend s) (caddr s))
(define (make-sum a1 a2) (list '+ a1 a2))
(define (product? x) (and (pair? x) (eq? (car x) '*)))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))
(define (make-product m1 m2) (list '* m1 m2))2.7 通用型操作与数据导向编程
当系统需要处理多种数据类型时，如何设计通用的操作接口？这是数据导向编程（data-directed programming）要解决的问题。
类型标签方法：给数据对象添加类型标签，使通用操作可以根据类型分派：
(define (attach-tag tag contents) (cons tag contents))
(define (type-tag datum)
(if (pair? datum) (car datum)
(error "Bad tagged datum -- TYPE-TAG" datum)))
(define (contents datum)
(if (pair? datum) (cdr datum)
(error "Bad tagged datum -- CONTENTS" datum)))数据导向分派：使用操作-类型表来查找对应的实现：
(define *op-table* (make-table))
(define (put op type item)
((get 'put) *op-table* op type item))
(define (get op type)
((get 'get) *op-table* op type))
(define (install-rectangular-package)
(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (make-from-real-imag x y) (cons x y))
(define (magnitude z)
(sqrt (+ (square (real-part z))
(square (imag-part z)))))
(define (angle z)
(atan (imag-part z) (real-part z)))
(define (make-from-mag-ang r a)
(cons (* r (cos a)) (* r (sin a))))
(put 'real-part '(rectangular) real-part)
(put 'imag-part '(rectangular) imag-part)
(put 'magnitude '(rectangular) magnitude)
(put 'angle '(rectangular) angle)
(put 'make-from-real-imag '(rectangular) make-from-real-imag)
(put 'make-from-mag-ang '(rectangular) make-from-mag-ang)
'done)这种设计允许系统独立添加新的数据类型和新的操作，而无需修改现有代码。这就是开闭原则（Open-Closed Principle）的体现：对扩展开放，对修改关闭。
2.8 消息传递
消息传递（message passing）是另一种实现通用操作的方法。在消息传递风格中，数据对象被表示为过程，该过程接受一个"消息"作为参数，根据消息返回相应的操作结果。
(define (make-from-real-imag x y)
(define (dispatch op)
(cond ((eq? op 'real-part) x)
((eq? op 'imag-part) y)
((eq? op 'magnitude)
(sqrt (+ (square x) (square y))))
((eq? op 'angle)
(atan y x))
(else (error "Unknown op -- MAKE-FROM-REAL-IMAG" op))))
dispatch)
(define (apply-generic op arg) (arg op))这里 make-from-real-imag 返回一个过程 dispatch，该过程根据消息 op 返回相应的值或执行相应的操作。数据对象本身就是过程，这就是"数据作为过程"的观点。
消息传递是面向对象编程的基础。在面向对象语言中，对象接受消息并根据消息执行相应操作的模式，正是源于消息传递的思想。
重要知识点
1. 数据抽象的三层结构
数据抽象通常包含三层：
- 使用层：使用数据抽象接口的程序
- 抽象层：定义数据抽象接口（构造器和选择器）
- 表示层：数据的具体实现
这种分层结构使得我们可以独立修改每一层，而不影响其他层。例如，我们可以修改有理数的表示方式（从 pair 改为其他结构），只要保持 make-rat、numer、denom 的接口不变，使用层的代码就不需要修改。
2. 闭包性质
在 Scheme 中，cons 具有闭包性质（closure property）：任何由 cons 构造的对象，其元素也可以是 cons 构造的对象。这意味着我们可以用 cons 构建任意复杂的数据结构。
闭包性质是构建层次数据结构的基础。没有闭包性质，我们就只能用 cons 构建扁平的结构，无法表达树、图等复杂结构。
需要注意的是，这里的"闭包"与第一章中提到的闭包（closure）概念不同。在代数中，一个集合对某个操作封闭，意味着对该集合的元素应用该操作，结果仍在集合中。Scheme 的 cons 对 pair 集合封闭：对任何两个对象（包括 pair）应用 cons，结果仍是 pair。
3. 约定式接口
使用序列操作（map、filter、accumulate）时，我们建立了一种约定式接口（conventional interface）。只要数据可以表示为序列，就可以使用这组通用操作来处理。
约定式接口使得我们可以灵活组合各种操作，构建复杂的处理流程。例如：
(define (salary-of-highest-paid-programmer records)
(accumulate max 0
(map salary
(filter programmer? records))))这种风格类似于 Unix 管道的思想：每个操作接受序列，返回序列，可以像管道一样串联起来。
4. 嵌套映射
嵌套映射（nested mapping）是处理层次结构的重要技术。通过将映射操作嵌套使用，可以生成和处理多维数据结构。
; 生成所有小于 n 的 (i, j) 对，使得 i + j 是素数
(define (prime-sum-pairs n)
(map make-pair-sum
(filter prime-sum?
(flatmap
(lambda (i)
(map (lambda (j) (list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))))flatmap 是嵌套映射的辅助过程，它将映射结果展平为一层：
(define (flatmap proc seq)
(accumulate append nil (map proc seq)))5. 数据作为过程
数据不仅可以是结构，还可以是过程。通过将数据表示为过程，我们可以实现延迟求值、流等高级技术。
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument not 0 or 1 -- CONS" m))))
dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))这个实现展示了 cons、car、cdr 可以用纯过程来实现，不需要任何特殊的数据结构。这是 Church 编码（Church encoding）的一个例子，展示了用 lambda 演算表示数据的可能性。
常见误区
1. 混淆 quote 和 list
初学者经常混淆 '(...) 和 (list ...) 的区别。'(...) 创建的是符号列表，其中的元素是符号；(list ...) 创建的是值的列表，其中的元素是表达式的求值结果。
'(a b c) ; 符号列表 (a b c)
(list 1 2 3) ; 数值列表 (1 2 3)
(list a b c) ; 如果 a=1, b=2, c=3，结果为 (1 2 3)2. 忽略数据抽象的重要性
有些开发者倾向于直接操作数据的内部表示，而不是通过抽象接口。这种做法会使得代码与特定的数据表示紧密耦合，难以修改和扩展。始终应该通过构造器和选择器来操作数据，保持抽象屏障的完整性。
3. 对 map 和 for-each 的混淆
map 返回一个新列表，包含对每个元素应用过程的结果；for-each 对每个元素应用过程，但不返回有意义的结果（用于产生副作用）。
(map print (list 1 2 3)) ; 返回 (1 2 3)，同时打印 1 2 3
(for-each print (list 1 2 3)) ; 打印 1 2 3，返回值无意义4. 不正确处理树结构
处理树结构时，需要区分叶子节点和内部节点。叶子节点是原子值，内部节点是子树。递归处理树时，基本情况应该是空树或叶子节点。
; 错误：没有处理叶子节点
(define (count-leaves tree)
(if (null? tree)
0
(+ 1 (count-leaves (cdr tree))))) ; 忽略了 (car tree) 可能是叶子
; 正确
(define (count-leaves tree)
(cond ((null? tree) 0)
((not (pair? tree)) 1) ; 处理叶子节点
(else (+ (count-leaves (car tree))
(count-leaves (cdr tree))))))5. 对 eq? 和 equal? 的误用
eq? 判断两个对象是否是同一个对象（指针相等），equal? 判断两个对象的结构是否相同（值相等）。对于符号，eq? 和 equal? 通常等价；对于数字和字符串，应该使用 equal? 或专门的比较过程（如 =、string=?）。
(eq? '(1 2 3) '(1 2 3)) ; 可能返回 #f（两个不同的列表对象）
(equal? '(1 2 3) '(1 2 3)) ; 返回 #t（结构相同）
(eq? 'a 'a) ; 返回 #t（同一个符号）实践应用
1. 图形语言
本章介绍了一种使用画家（painter）抽象来构建图形语言的方法。画家是一种可以在指定框架内绘制图形的抽象。通过组合画家，可以创建复杂的图案。
(define (beside painter1 painter2)
(let ((split-point (make-vect 0.5 0.0)))
(let ((paint-left
(make-frame (origin-frame frame1)
(horiz-unit frame1)
(vert-unit frame1)))
(paint-right
(make-frame (add-vect (origin-frame frame2) split-point)
(scale-vect 0.5 (horiz-unit frame2))
(vert-unit frame2))))
(lambda (frame)
(painter1 paint-left)
(painter2 paint-right)))))通过 beside（并排）、below（上下）、flip-vert（垂直翻转）、flip-horiz（水平翻转）等基本操作，可以构建出复杂的分形图案，如 Escher 风格的画作。
2. 符号计算
符号微分、符号积分、代数化简等都是符号计算的应用。通过将数学表达式表示为符号列表，可以使用程序来操作这些表达式。
; 代数化简：将 (+ x 0) 简化为 x
(define (make-sum a1 a2)
(cond ((=number? a1 0) a2)
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
(else (list '+ a1 a2))))3. 集合操作
集合是数学和计算机科学中的基本概念。Scheme 提供了多种表示集合的方法：
无序列表表示：
(define (element-of-set? x set)
(cond ((null? set) #f)
((equal? x (car set)) #t)
(else (element-of-set? x (cdr set)))))
(define (adjoin-set x set)
(if (element-of-set? x set)
set
(cons x set)))
(define (union-set set1 set2)
(cond ((null? set1) set2)
((element-of-set? (car set1) set2)
(union-set (cdr set1) set2))
(else (cons (car set1) (union-set (cdr set1) set2)))))有序列表表示（效率更高）：
(define (element-of-set? x set)
(cond ((null? set) #f)
((= x (car set)) #t)
((< x (car set)) #f)
(else (element-of-set? x (cdr set)))))二叉树表示（效率最高）：
(define (element-of-set? x set)
(cond ((null? set) #f)
((= x (entry set)) #t)
((< x (entry set))
(element-of-set? x (left-branch set)))
((> x (entry set))
(element-of-set? x (right-branch set)))))4. Huffman 编码
Huffman 编码是一种用于数据压缩的前缀编码方法。本章介绍了如何使用 Scheme 构建 Huffman 编码树和解码器。
(define (make-leaf symbol weight)
(list 'leaf symbol weight))
(define (make-code-tree left right)
(list left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))
(define (decode bits tree)
(define (decode-1 bits current-branch)
(if (null? bits)
'()
(let ((next-branch
(choose-branch (car bits) current-branch)))
(if (leaf? next-branch)
(cons (symbol-leaf next-branch)
(decode-1 (cdr bits) tree))
(decode-1 (cdr bits) next-branch)))))
(decode-1 bits tree))5. 信息检索
序列操作可以用于实现简单的信息检索系统。通过将记录表示为列表，可以使用 filter 和 map 来查询和转换数据。
; 查找工资高于某个阈值的所有员工
(define (high-salary-employees records threshold)
(filter (lambda (record)
(> (salary record) threshold))
records))
; 计算所有程序员的平均工资
(define (average-programmer-salary records)
(let ((programmers (filter programmer? records)))
(/ (accumulate + 0 (map salary programmers))
(length programmers))))本章小结
本章深入探讨了数据抽象的概念和技术。我们学习了：
数据抽象：通过将数据的使用与表示分离，建立抽象屏障，使得程序更加模块化和可维护。构造器和选择器构成了数据的抽象接口。
Pair 与 List：cons、car、cdr 是构建复合数据的基本工具。列表是最重要的序列数据结构，支持递归遍历和各种操作。
序列操作：map、filter、accumulate 是处理序列的通用操作，可以组合使用实现复杂的数据处理。这种风格称为管道式编程或约定式接口。
层次数据结构：树是常见的层次结构，通过递归可以遍历和操作树。嵌套映射可以生成和处理多维数据。
符号数据：使用 quote 可以处理符号本身，而不是符号的值。符号数据在构建解释器、处理代数表达式等场景中非常重要。
数据导向编程：通过类型标签和操作-类型表，可以设计支持多种数据类型的通用操作。这种设计支持独立扩展。
消息传递：将数据表示为过程，根据消息执行相应操作。这是面向对象编程的基础。
数据作为过程：cons、car、cdr 可以用纯 lambda 表达式实现，展示了数据与过程的等价性。
这些概念和技术构成了现代程序设计的基础。数据抽象的原则——接口与实现分离、抽象屏障、约定式接口——在大型软件系统中尤为重要。掌握这些技术，可以帮助我们构建更加清晰、灵活、可维护的程序。
在下一章中，我们将学习如何引入状态和赋值，从函数式编程转向命令式编程，探讨模块化、对象和状态的管理。