序对就是一种通用的建筑砌块,通过它可以构造起所有不同种类的数据结构。这里建立的元素本省也是序对的序对,这就是表结构得以作为一种表示工具的根本基础。我们将这种能力称为cons的 闭包性质。一般来说如果某种组合数据对象满足闭包性质,那就是说,通过它组合起来的数据对象的得到的结果本生还可以通过同样的操作再进行组合。
序列的表示(这里我理解为链表)
通过嵌套cons形成的这样的一个序对的序列称为一个表,Scheme为了方便表的构造,提供了一个基本操作list。
这里可以将car看作选取表的第一项的操作,将cdr看作是选取表中除去第一项之后剩下的所有项形成的子表。car和cdr的嵌套应用可以取出第一个表里的第二、第三以及后面的各项,构造符cons可用于构造表,它在原有的表前面增加一个元素。
利用序对将元素的序列表示为表之后,我们就可以使用常规的程序设计技术,通过顺序“向下cdr”表的方式完成对表的各种操作。下面的过程list-ref
的实际参数是一个表和一个数n,它返回这个表中的第n个项,这里人们习惯将表的元素的编号从0开始,计算list-ref
的方法如下:
* 对n=0,list-ref
返回表的car
* 否则,list-ref
返回表的cdr的第(n-1)个项。
在表的操作过程中,要学习强调从元素表到结果表的变换,而不是注意在逐个元素的处理上。
层次性结构
将表作为序列的表示方式,可以很自然的推广到表示那些元素本省也是序列的序列。认识这种元素本身也是序列的序列的一种方式,就是将它们看作树。序列中的元素就是树的分支,而那些本身也是序列的元素就形成了树中的子树。递归是处理树结构的一种很自然的工具,因为我们常常可以将对于树的操作归结为对它们分支的操作,再将这种操作归结为对分支的分支的操作,如此下去,直到达到树的叶子。
map是处理序列的一种强有力的抽象,与此类似,map与递归的结合也是处理树的一种强有力的抽象。
序列作为一种约定的界面
计算过程可以很自然的用流过一些级联的处理步骤的信号方式描述,其中的每个步骤都是实现程序方案中的一个部分。对于一种情况sum-odd-squares
。这里从一个 枚举器 开始,它产生出给定树的所有树叶组成的“信号”。这一信号流过一个过滤器,后将所有所有的不是奇数的数都删除,这样得到的信号又通过一个映射,这是一个“转换装置”,它将square过程应用于每个元素。这一映射的输出被馈入一个积累器,该装置用+将所有的元素组合起来,以初始0开始。
要组织好这些程序使之能够更清晰的的反应上面信号流的结构,最关键的一点就是将注意力集中在处理过程从一个步骤流向下一个步骤的“信号”
将程序表示为一些针对序列的操作,这样做的价值就在能帮助我呢吧得到模块化的程序设计,也就是说,得到由一些比较独立的片段组合构成设计。通过提供一个标准部件的库,并使这些部件都有着一些能以各种灵活方式互相链接的约定界面。