范围

进入第二章——构造数据抽象

keywords：数据复合、数据抽象、抽象屏障。序对、闭包性、序列。映射。
程序： list-ref、append、reverse；map；for-each

抽象数据导引

什么是数据抽象？

过程抽象中，构造更复杂的过程，就把一个过程用作其中的元素。比如说 平方和 过程的实现中使用了求平方和加和两个过程，构造更复杂的过程时，元素的实现细节被隐藏了。对平方和来说，这就构造了抽象——这一过程的使用方式，与该过程如何通过更基本的过程实现的具体细节相分离。

针对数据的类似概念就是数据抽象，数据抽象是一种方法学。一个复合数据对象的使用，应该与是怎么由更基本的数据对象构造的细节隔离开的。

前一章中，涉及的数字，只是一些基础的数字和数值运算。第二章开始，我们要考察更复杂的数据。就像简单的过程可以复合形成复合过程，将数据对象组合起来，形成复合数据。

复合数据的意义：

提升我们在程序设计时所位于的概念层次。
提高设计的模块性。
增强语言的表达能力。

比如，要完成一个对分数进行运算的程序。若将一个分数看成一个分子和一个分母，分别用两个变量来代表。这样做下去，会非常难受，要记得哪一个分母和哪一个分子对应，这种杂乱麻烦的记录工作会严重搅乱程序设计。若是能将两个变量“合在一起”，形成一个复合数据，情况就好得多。

对分数的操作就可以将这一个复合数据当做一个概念上的单位，提升了层次。
进一步提高程序的模块性。也就是说，处理分数的那些程序部分，与分数如何表达的细节隔离开了。这种把数据对象的使用部分和表示细节部分相分离的技术思想非常具有一般性，这就是被称为数据抽象的强有力的设计方法学。
复合对象的使用最重要的是真正地提高了语言的表达能力。举最简单的“线性组合”：$ax + by$为例，我们想到写一个过程接受四个参数返回$ax + by$的值，那么就是下面这个样子：

1 2	(define (linear-combination a b x y) (+ (* a x) (* b y)))

但是，如果编程语言的表达能力更强，所针对的不仅仅是简单数据，而是分数、复数、多项式等等其他东西的话，应该是下面这个样子：

1 2	(define (linear-combination a b x y) (add (mul a x)(mul b y)))

add和mul 也不是简单的加法和乘法了，而是更复杂的内在。从抽象的意义来看，对于过程linear-combination来说，这里的 a、b、x、y 是什么，根本没有关系。这个例子也说明了，为什么一种程序设计语言要提供一种复合简单对象的方法，以及直接操作符合对象的能力，是多么的重要。

复合简单数据的方法就是程序设计语言应该提供某种“粘合剂”用于把简单数据对象组合起来，形成复杂的数据对象。在复合的思想中有一个关键的概念——闭包，就是粘合剂不但能组合基本的数据，还可以粘合复杂的数据对象（形成更复杂的数据对象）。

除此之外，还将看到，数据抽象能让程序在不同的层次之间建立起抽象屏障。这个知识点就像是网络的 OSI 七层模型，或者说“用户——软件——操作系统——硬件”的层次，概念是相同的。

序对

剧透：序对可以用做构造任意种类的复杂数据结构的通用的基本构件。

序对其实和离散数学中的“有序对”没什么差别。具体到 Scheme 语言里，有一个基本过程：cons，需要两个参数，返回一个包含这两个参数作为其成分的符合数据对象。对于一个由cons构造的序对，基本过程car和cdr可以取出前后两个部分。

(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))

(car x)

(cdr y)

(car z)

(car ( cdr z))


结果：
1
4
(mcons 1 2)
3

Closure Property

介绍一个重要的概念，cons 的闭包性质。

闭包性质这一术语来自抽象代数（离散数学也有），意思是一集元素在某个运算下封闭，封闭是指这个运算运用于一集合中的元素，产出的仍然是该集合的元素。

如图所示，由于闭包性，你可以不仅可以用 cons去组合数值，还可以用cons组合序对！这一性质，通过它可以构造出许多不同种类的数据结构来。闭包性质是 cons 组合威力的关键要素，它能用来构建出层次性结构的数据对象。

非常有意思的性质，对不对？联系一下 C 语言，我们可以发现其实 C 语言提供的数据组合方法并不具备这种性质。例如 struct 是可以包含别的 struct，但是要求程序员显示地操纵指针（也就是别的东西，而不是数据对象本身），并限制性地要求struct里面包含的只能是预先定义好的元素。

Alan Perlis 评价：“……过多的可声明数据结构导致了函数的专用化，造成了对合作的阻碍。让 100 个函数在一个数据结构上操作，远比让 10 个函数在 10 个数据结构上操作更好些。”

Squence

利用序对构造出的一类有用结构就是序列（Sequence）。定义也非常简单，看下图就行。与我们熟知的表很想，但我觉得链表（linked list）特指那种有一个数据对象和一个指针构成的数据结构。序列更适合本书语境。

可以像图上那样写很多 cons 复合来构成表。为了方便表的构造，Scheme 有一个基础操作list。简单来说(list 1 2 3 4)就等同于上面那一堆 cons 的结果。

(define one-through-four (list 1 2 3 4))

(car one-through-four)

(cdr one-through-four)

;结果：
1
(mcons 2 (mcons 3 (mcons 4 '())))

对表来说，car就是选取表的第一项，cdr就是选取表中除去第一项之后剩下元素形成的子表。嵌套应用car和cdr可以取出表的各项。

cons 只能用于在原有表的前面增加一个元素，因为表尾最后一个元素应该是nil。

(define one-through-four (list 1 2 3 4))
(cons 10 one-through-four)


;结果：
(mcons
 10
 (mcons
  1
  (mcons
   2
   (mcons 3 (mcons 4 '())))))

;用 cons 在后添加是错误的
(define one-through-four (list 1 2 3 4))
(cons  one-through-four 10)

;结果：
(mcons
 (mcons
  1
  (mcons
   2
   (mcons 3 (mcons 4 '()))))
 10)

(list 1 2 3 4 10)

;结果：
(mcons
 1
 (mcons
  2
  (mcons
   3
   (mcons 4 (mcons 10 '())))))

一些函数

;取出列表的第n项
(define (list-ref L n)
  (if (= n 0)
      (car L)
      (list-ref (cdr L)(- n 1))))

(define squares (list 1 4 9 16 25))

(list-ref squares 3)

;求表长
;null? 是基本过程，检查参数是不是空表
(define (length L)
  (if (null? L)
      0
      (+ 1 (length (cdr L)))))

(length squares)


;连接两个表
(define (append L1 L2)
  (if (null? L1)
      L2
      (cons (car L1) (append (cdr L1)L2))))

(define odds (list 1 3 5 7 9))

(append squares odds)


;习题1：求表最后一个元素，迭代
(define (last-pair L)
  (if (null? (cdr L))
      L
      (last-pair (cdr L))))

(last-pair squares)

;习题2：表逆序
(define (reverse L)(reverse-iter L nil))

(define (reverse-iter list other)
  (if (null? list)
      other
      (reverse-iter (cdr list)(cons(car list) other))))

(reverse squares)

尤其是表逆序这一题，我看着代码看了很久。思考它与典型的过程化语言C语言打出来的链表逆序有什么不同。可以看出，表逆序是一个递归过程。在前面的学习中，知道了递归的意思就是与操作延迟推行。表逆序这个过程，若list为空，other便为输出结果。other最初是nil，会直接递归执行到原表 L 的尾部，递归开始返回。从倒数第一个元素，用cons 将其加到 other前面，就完成了这一过程。

这也是 SICP 给我几个最大的触动之一。简单的序对就能够构成很多已知的数据结构，比如说树、还有链表，像类似于什么求链表长度、求树的深度这样子的函数都能够用看上去十分玄幻，但细看十分精妙的几行 scheme 就能写成。光是知道了这几点，我觉得都已经让我觉得非常满足了。

映射（map）

将某种变换应用于一个表的所有元素得到一个由所有结果构成的新表。

(define (scale-list items factor)
  (if (null? items)
      nil
      (cons (* (car items) factor)
            (scale-list (cdr items) factor))))


(scale-list (list 1 2 3 4 5) 10)
(10 20 30 40 50)

仍然，可以继续抽象这一想法，将其中的公共模式抽象成高阶过程。这一高阶过程就是映射（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 5))
(1 4 9 16 25)

map 建立起了对表处理的高级抽象。

在原来的 scale-list 里面，我们的注意力被吸引到了如何对每个元素做处理上。而通过抽象成 map 省略了细节上的层面。
这两种形式定义的差别，不会让计算机进行不同的计算过程，而是让我们对同一个过程有了一种不同的思考方式。
map 帮我们建立了一层抽象屏障，实现了映射操作，而与如何提取表中元素、如何对每个元素进行操作的细节隔离开了。

接下来的练习题中就给出了很生动的例子：过程square-list返回序列中每个数的平方构成的新序列。第一个定义就是过程性语言中的迭代：

(define (square x) (* x x))

(define (square-list items)
  (if (null? items)
      nil
      (cons (square (car items))(square-list (cdr items)))))

(square-list (list 1 2 3 4 5))

其实观察可以发现，内部的过程其实是和map很相似的，这就是为何要抽象的原因。

(define (square x) (* x x))
 
(define (square-list items)
  (map square items))

(square-list (list 1 2 3 4 5))

老赵书托中，就提到了这个例子：

如果您理解了上面的代码，其实您已经对函数式编程更细致的抽象能力有所体会了。……目前函数式编程几乎已经成了高级语言的必备特性了，如C#，F#，甚至颇有代替Java语言之势的Scala中也包含了相当的函数式编程能力。事实上，我认为出现这种趋势的一个重要原因，便在于人们之前对面向对象语言的抽象能力寄予过高期望，而这种期望的破灭（或者说“冷静”）使得许多人的注意力又回到了更容易“组合”和“复用”的函数式编程理念上。而且，其实人们从来没有放弃过对小粒度的事物的热爱。例如很多人喜欢C语言的原因，便是因为它没有庞大的架构，可以通过各种方法的组装来编写程序。而Unix编程艺术之一，便是大量小程序的组合复用。

for-each

for-each 与 map 类似，但它并不返回结果的表，而是把过程应用于各个元素，而得到的值都丢弃不用。返回值是一些其他的东西，例如逻辑值真。

(define (for-each proc items)
  (cond ((not (null? items))
         (proc (car items))             ;仅将过程应用于各个元素
         (for-each proc (cdr items))))) ;满足条件就继续应用下一个。应用 proc 得到的值都丢弃不用 

(for-each (lambda(x) (newline) (display x))
          (list 1 2 3))