Exercise 2.39 · 习题

Exercise 2.39: Complete the following
definitions of reverse (Exercise 2.18) in terms of
fold-right and fold-left from Exercise 2.38:

(define (reverse sequence)
(fold-right
(lambda (x y) ⟨??⟩) nil sequence))

(define (reverse sequence)
(fold-left
(lambda (x y) ⟨??⟩) nil sequence))

Nested Mappings

We can extend the sequence paradigm to include many computations that are
commonly expressed using nested loops. Consider this problem: Given a positive integer n, find all
ordered pairs of distinct positive integers i and j, where
1
≤
j

i
≤
n, such that i
+
j is prime. For example, if n is 6,
then the pairs are the following:
i

2

3

4

4

5

6

6

j

1

2

1

3

2

1

5

i
+
j

3

5

5

7

7

7

11
A natural way to organize this computation is to generate the sequence of all
ordered pairs of positive integers less than or equal to n, filter to
select those pairs whose sum is prime, and then, for each pair (
i
,
j
)
that passes through the filter, produce the triple (
i
,
j
,
i
+
j
).

Here is a way to generate the sequence of pairs: For each integer i
≤
n,
enumerate the integers j

i, and for each such i and j
generate the pair (
i
,
j
). In terms of sequence operations, we map along
the sequence (enumerate-interval 1 n). For each i in this sequence,
we map along the sequence (enumerate-interval 1 (- i 1)). For each
j in this latter sequence, we generate the pair (list i j). This
gives us a sequence of pairs for each i. Combining all the sequences for
all the i (by accumulating with append) produces the required
sequence of pairs:

(accumulate
append
nil
(map (lambda (i)
(map (lambda (j)
(list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))

The combination of mapping and accumulating with append is so common in
this sort of program that we will isolate it as a separate procedure:

(define (flatmap proc seq)
(accumulate append nil (map proc seq)))

Now filter this sequence of pairs to find those whose sum is prime. The filter
predicate is called for each element of the sequence; its argument is a pair
and it must extract the integers from the pair. Thus, the predicate to apply
to each element in the sequence is

(define (prime-sum? pair)
(prime? (+ (car pair) (cadr pair))))

Finally, generate the sequence of results by mapping over the filtered pairs
using the following procedure, which constructs a triple consisting of the two
elements of the pair along with their sum:

(define (make-pair-sum pair)
(list (car pair)
(cadr pair)
(+ (car pair) (cadr pair))))

Combining all these steps yields the complete procedure:

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

Nested mappings are also useful for sequences other than those that enumerate
intervals. Suppose we wish to generate all the permutations of a set S
;
that is, all the ways of ordering the items in the set. For instance, the
permutations of {
1
,
2
,
3
} are {
1
,
2
,
3
}, {
1
,
3
,
2
}, {
2
,
1
,
3
}, {
2
,
3
,
1
},
{
3
,
1
,
2
}, and {
3
,
2
,
1
}. Here is a plan for generating the permutations of
S: For each item x in S, recursively generate the sequence of
permutations of S
−
x, and adjoin x to the front of each one.
This yields, for each x in S, the sequence of permutations of S
that begin with x. Combining these sequences for all x gives all the
permutations of S:

(define (permutations s)
(if (null? s) ; empty set?
(list nil) ; sequence containing empty set
(flatmap (lambda (x)
(map (lambda (p)
(cons x p))
(permutations
(remove x s))))
s)))

Notice how this strategy reduces the problem of generating permutations of
S to the problem of generating the permutations of sets with fewer elements
than S. In the terminal case, we work our way down to the empty list,
which represents a set of no elements. For this, we generate (list
nil), which is a sequence with one item, namely the set with no elements. The
remove procedure used in permutations returns all the items in a
given sequence except for a given item. This can be expressed as a simple
filter:

(define (remove item sequence)

(filter (lambda (x) (not (= x item)))

sequence))

练习 2.39：用练习 2.38 中的 fold-right 和 fold-left，完成下列 reverse（练习 2.18）的定义：

(define (reverse sequence)
(fold-right
(lambda (x y) ⟨??⟩) nil sequence))

(define (reverse sequence)
(fold-left
(lambda (x y) ⟨??⟩) nil sequence))

嵌套映射

我们可以将序列范式扩展，用以表达许多通常用嵌套循环来表述的计算。考虑这样一个问题：给定正整数 n，找出所有满足 1 ≤ j < i ≤ n 的不同正整数有序对 i 和 j，使得 i + j 是素数。例如，当 n 为 6 时，满足条件的序对如下：

i 2 3 4 4 5 6 6

j 1 2 1 3 2 1 5

i+j 3 5 5 7 7 7 11

组织这一计算的自然方式是：先生成所有不大于 n 的正整数有序对的序列，过滤出其和为素数的序对，然后对通过过滤的每个序对 (i, j) 产生三元组 (i, j, i+j)。

以下是生成序对序列的一种方式：对每个整数 i ≤ n，枚举所有满足 j < i 的整数 j，对每组 i 和 j 生成序对 (list i j)。就序列操作而言，我们沿序列 (enumerate-interval 1 n) 进行映射。对该序列中的每个 i，再沿序列 (enumerate-interval 1 (- i 1)) 进行映射。对后一序列中的每个 j，生成序对 (list i j)。这样，对每个 i 得到一个序对的序列。将所有 i 的序列合并（通过以 append 作为运算的累积），便得到所需的序对序列：

(accumulate
append
nil
(map (lambda (i)
(map (lambda (j)
(list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))

在此类程序中，映射与以 append 进行的累积的组合十分常见，我们将其单独定义为一个过程：

(define (flatmap proc seq)
(accumulate append nil (map proc seq)))

接着对这个序对序列进行过滤，找出其和为素数的序对。过滤谓词对序列的每个元素进行调用，其参数是一个序对，因此必须从序对中取出整数。对序列中每个元素施用的谓词为

(define (prime-sum? pair)
(prime? (+ (car pair) (cadr pair))))

最后，对过滤后的序对进行映射，用如下过程生成结果序列，该过程构造一个由序对两个元素及其和组成的三元组：

(define (make-pair-sum pair)
(list (car pair)
(cadr pair)
(+ (car pair) (cadr pair))))

将所有这些步骤组合起来，得到完整的过程：

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

嵌套映射对于枚举区间以外的序列同样有用。假设我们希望生成集合 S 的所有排列，即对集合中的元素进行所有可能排列的方式。例如，{1, 2, 3} 的排列为 {1, 2, 3}、{1, 3, 2}、{2, 1, 3}、{2, 3, 1}、{3, 1, 2} 和 {3, 2, 1}。以下是生成 S 的排列的方案：对 S 中的每个元素 x，递归地生成 S - x 的所有排列序列，并将 x 添加到每个排列的最前面。这样，对 S 中每个 x，得到以 x 开头的所有 S 的排列序列。将所有 x 的这些序列组合起来，即得到 S 的全部排列：

(define (permutations s)

(if (null? s) ; 空集？

(list nil) ; 含空集的序列

(flatmap (lambda (x)

(map (lambda (p)

(cons x p))

(permutations

(remove x s))))

s)))

注意这一策略如何将生成 S 的排列问题化归为生成元素个数少于 S 的集合的排列。在终止情况下，我们一路化归到空表，它表示不含任何元素的集合。对此，我们生成 (list nil)，即包含一个元素（即空集）的序列。permutations 中使用的 remove 过程返回给定序列中除给定元素外的所有元素，可以表述为一个简单的过滤：

(define (remove item sequence)
(filter (lambda (x) (not (= x item)))
sequence))