列表处理工具箱

不难看出, 列表可以作为表示有限序列的通用媒介.  围绕这一媒介, 我们可以设计一组通用的处理过程. 这些过程可以自由地进行组合, 就像搭积木一样简单.

1. map

最具有代表性的列表处理过程应该就是map了, 它将一个函数应用于列表的每个元素上.

一种可能的map定义如下.

其中null?是一个谓词, 对于空表返回#t, 否则返回#f.

想必读者对于map还不甚熟悉, 让我们来计算一个例子.

2. filter

filter从列表中过滤出满足谓词的元素.

一种可能的filter定义如下.

以下是一些例子.

3. append

append将两个列表连接起来.

注记. 从append的定义可以看出, 其实第二个参数不是列表也可以.

以下是一些例子.

4. reverse

reverse反转一个列表.

以下是一些例子.

注记. reverse当然也可以按照如下方式定义, 就是效率看上去就会很尴尬.

5. fold-left和fold-right

fold-left和fold-right, 在某种程度上说, 提供了对于列表处理过程的抽象.

因为fold-left和fold-right比较复杂, 我们先举例子.

现在我们给出fold-left和fold-right的定义.

为了说明fold-left和fold-right何以为抽象, 我们用它们来重新定义之前的列表处理过程.

练习. 我们给出的fold-right的定义呈现出递归计算行为, 试将其改写为呈现迭代计算行为的版本.

你的回應