Exercise 2.20 · 习题

Exercise 2.20: The procedures +,
*, and list take arbitrary numbers of arguments. One way to
define such procedures is to use define with
dotted-tail notation.
In a procedure definition, a parameter list that has a dot before
the last parameter name indicates that, when the procedure is called, the
initial parameters (if any) will have as values the initial arguments, as
usual, but the final parameter’s value will be a
list of any
remaining arguments. For instance, given the definition

(define (f x y . z) ⟨body⟩)

the procedure f can be called with two or more arguments. If we
evaluate

(f 1 2 3 4 5 6)

then in the body of f, x will be 1, y will be 2, and
z will be the list (3 4 5 6). Given the definition

(define (g . w) ⟨body⟩)

the procedure g can be called with zero or more arguments. If we
evaluate

(g 1 2 3 4 5 6)

then in the body of g, w will be the list (1 2 3 4 5
6).

Use this notation to write a procedure same-parity that takes one or
more integers and returns a list of all the arguments that have the same
even-odd parity as the first argument. For example,

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

(same-parity 2 3 4 5 6 7)
(2 4 6)

Mapping over lists

One extremely useful operation is to apply some transformation to each element
in a list and generate the list of results. For instance, the following
procedure scales each number in a list by a given factor:

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

We can abstract this general idea and capture it as a common pattern expressed
as a higher-order procedure, just as in 1.3. The higher-order
procedure here is called map. Map takes as arguments a procedure
of one argument and a list, and returns a list of the results produced by
applying the procedure to each element in the list:

(define (map proc items)
(if (null? items)
nil
(cons (proc (car items))
(map proc (cdr items)))))

(map abs (list -10 2.5 -11.6 17))
(10 2.5 11.6 17)

(map (lambda (x) (* x x)) (list 1 2 3 4))
(1 4 9 16)

Now we can give a new definition of scale-list in terms of map:

(define (scale-list items factor)
(map (lambda (x) (* x factor))
items))

Map is an important construct, not only because it captures a common

pattern, but because it establishes a higher level of abstraction in dealing

with lists. In the original definition of scale-list, the recursive

structure of the program draws attention to the element-by-element processing

of the list. Defining scale-list in terms of map suppresses that

level of detail and emphasizes that scaling transforms a list of elements to a

list of results. The difference between the two definitions is not that the

computer is performing a different process (it isn’t) but that we think about

the process differently. In effect, map helps establish an abstraction

barrier that isolates the implementation of procedures that transform lists

from the details of how the elements of the list are extracted and combined.

Like the barriers shown in Figure 2.1, this abstraction gives us the

flexibility to change the low-level details of how sequences are implemented,

while preserving the conceptual framework of operations that transform

sequences to sequences. Section 2.2.3 expands on this use of sequences

as a framework for organizing programs.

练习 2.20：过程 +、* 和 list 接受任意数量的参数。定义此类过程的一种方式是使用带点尾记法 (dotted-tail notation) 的 define。在过程定义中，若参数表在最后一个参数名前有一个点，则表示：当过程被调用时，初始参数（若有）照常绑定到初始实参，而最后一个参数的值将是所有剩余实参构成的表。例如，对于定义

(define (f x y . z) ⟨体⟩)

过程 f 可以用两个或更多参数调用。若我们求值

(f 1 2 3 4 5 6)

则在 f 的体中，x 为 1，y 为 2，z 为表 (3 4 5 6)。对于定义

(define (g . w) ⟨体⟩)

过程 g 可以用零个或更多参数调用。若我们求值

(g 1 2 3 4 5 6)

则在 g 的体中，w 为表 (1 2 3 4 5 6)。

使用这种记法，编写过程 same-parity，它取一个或更多整数，返回由与第一个参数奇偶性相同的所有参数构成的表。例如：

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

(same-parity 2 3 4 5 6 7)
(2 4 6)

表的映射

一种极为有用的操作是对表中的每个元素施用某种变换，并生成结果的表。例如，下面的过程将表中的每个数按给定因子缩放：

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

我们可以抽象这个一般性思路，将其捕捉为一个公共模式，并用高阶过程来表达，就像在 1.3 节中所做的那样。这里的高阶过程称为 map。map 以一个单参数过程和一个表为参数，返回对表中每个元素施用该过程后产生的结果表：

(define (map proc items)
(if (null? items)
nil
(cons (proc (car items))
(map proc (cdr items)))))

(map abs (list -10 2.5 -11.6 17))
(10 2.5 11.6 17)

(map (lambda (x) (* x x)) (list 1 2 3 4))
(1 4 9 16)

现在，我们可以用 map 给出 scale-list 的新定义：

(define (scale-list items factor)
(map (lambda (x) (* x factor))
items))

map 是一个重要的构造，不仅因为它捕捉了一个公共模式，还因为它在处理表时建立了更高层次的抽象。在 scale-list 的原始定义中，程序的递归结构将注意力引向对表的逐元素处理。而用 map 定义 scale-list 则掩盖了这一层细节，强调了缩放是将一个元素表变换为结果表。两种定义的区别不在于计算机执行了不同的计算过程（它并没有），而在于我们以不同的方式思考这一计算过程。实际上，map 有助于建立一道抽象屏障，将变换表的过程的实现与提取和组合表中元素的细节相隔离。就像图 2.1 所示的那些屏障一样，这种抽象使我们能够灵活地改变序列实现的底层细节，同时保留将序列变换为序列的操作的概念框架。2.2.3 节将进一步展开以序列作为组织程序框架的这一用法。