Exercise 3.65 · 习题

Exercise 3.65: Use the series
ln
⁡
2

=

1
−

1
2

+

1
3

−

1
4

+
…
to compute three sequences of approximations to the natural logarithm of 2, in
the same way we did above for π. How rapidly do these sequences
converge?

Infinite streams of pairs

In 2.2.3, we saw how the sequence paradigm handles traditional
nested loops as processes defined on sequences of pairs. If we generalize this
technique to infinite streams, then we can write programs that are not easily
represented as loops, because the “looping” must range over an infinite set.

For example, suppose we want to generalize the prime-sum-pairs procedure
of 2.2.3 to produce the stream of pairs of all integers
(
i
,
j
) with i
≤
j such that i
+
j is prime. If
int-pairs is the sequence of all pairs of integers (
i
,
j
) with
i
≤
j, then our required stream is simply

(stream-filter
(lambda (pair)
(prime? (+ (car pair) (cadr pair))))
int-pairs)

Our problem, then, is to produce the stream int-pairs. More generally,
suppose we have two streams S
=
(

S
i

) and T
=
(

T
j

),
and imagine the infinite rectangular array
(

S
0

,

T
0

)

(

S
0

,

T
1

)

(

S
0

,

T
2

)

…

(

S
1

,

T
0

)

(

S
1

,

T
1

)

(

S
1

,

T
2

)

…

(

S
2

,

T
0

)

(

S
2

,

T
1

)

(

S
2

,

T
2

)

…

…
We wish to generate a stream that contains all the pairs in the array that lie
on or above the diagonal, i.e., the pairs
(

S
0

,

T
0

)

(

S
0

,

T
1

)

(

S
0

,

T
2

)

…

(

S
1

,

T
1

)

(

S
1

,

T
2

)

…

(

S
2

,

T
2

)

…

…
(If we take both S and T to be the stream of integers, then this will
be our desired stream int-pairs.)

Call the general stream of pairs (pairs S T), and consider it to be
composed of three parts: the pair (

S
0

,

T
0

), the rest of the pairs in
the first row, and the remaining pairs:
(

S
0

,

T
0

)

(

S
0

,

T
1

)

(

S
0

,

T
2

)

…

(

S
1

,

T
1

)

(

S
1

,

T
2

)

…

(

S
2

,

T
2

)

…

…
Observe that the third piece in this decomposition (pairs that are not in the
first row) is (recursively) the pairs formed from (stream-cdr S) and
(stream-cdr T). Also note that the second piece (the rest of the first
row) is

(stream-map (lambda (x)
(list (stream-car s) x))
(stream-cdr t))

Thus we can form our stream of pairs as follows:

(define (pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(⟨combine-in-some-way⟩
(stream-map (lambda (x)
(list (stream-car s) x))
(stream-cdr t))
(pairs (stream-cdr s)
(stream-cdr t)))))

In order to complete the procedure, we must choose some way to combine the two
inner streams. One idea is to use the stream analog of the append
procedure from 2.2.1:

(define (stream-append s1 s2)
(if (stream-null? s1)
s2
(cons-stream
(stream-car s1)
(stream-append (stream-cdr s1) s2))))

This is unsuitable for infinite streams, however, because it takes all the
elements from the first stream before incorporating the second stream. In
particular, if we try to generate all pairs of positive integers using

(pairs integers integers)

our stream of results will first try to run through all pairs with the first
integer equal to 1, and hence will never produce pairs with any other value of
the first integer.

To handle infinite streams, we need to devise an order of combination that
ensures that every element will eventually be reached if we let our program run
long enough. An elegant way to accomplish this is with the following
interleave procedure:

(define (interleave s1 s2)
(if (stream-null? s1)
s2
(cons-stream
(stream-car s1)
(interleave s2 (stream-cdr s1)))))

Since interleave takes elements alternately from the two streams, every
element of the second stream will eventually find its way into the interleaved
stream, even if the first stream is infinite.

We can thus generate the required stream of pairs as

(define (pairs s t)

(cons-stream

(list (stream-car s) (stream-car t))

(interleave

(stream-map (lambda (x)

(list (stream-car s) x))

(stream-cdr t))

(pairs (stream-cdr s) (stream-cdr t)))))

练习 3.65：利用级数 ln 2 = 1 − 1/2 + 1/3 − 1/4 + …，按照我们上面对 π 所做的方式，计算自然对数 2 的三个近似序列。这些序列收敛的速度如何？

序对的无穷流

在 2.2.3 节中，我们看到了序列范式如何将传统的嵌套循环处理为定义在序对序列上的计算过程。若将这一技术推广到无穷流，就可以编写难以用循环表示的程序，因为“循环”必须遍历无穷集合。

例如，假设我们想将 2.2.3 节的 prime-sum-pairs 过程推广为产生满足 i ≤ j 且 i + j 为质数的所有整数序对 (i, j) 的流。若 int-pairs 是满足 i ≤ j 的所有整数序对 (i, j) 的序列，则所求的流就是：

(stream-filter
(lambda (pair)
(prime? (+ (car pair) (cadr pair))))
int-pairs)

于是，问题归结为如何产生 int-pairs 这个流。更一般地，假设我们有两个流 S = (Sᵢ) 和 T = (Tⱼ)，设想一个无穷矩形数组：

(S₀, T₀) (S₀, T₁) (S₀, T₂) …

(S₁, T₀) (S₁, T₁) (S₁, T₂) …

(S₂, T₀) (S₂, T₁) (S₂, T₂) …

…

我们希望生成一个包含该数组对角线及其上方所有序对的流，即：

(S₀, T₀) (S₀, T₁) (S₀, T₂) …

(S₁, T₁) (S₁, T₂) …

(S₂, T₂) …

…

（若将 S 和 T 都取为整数流，这就是我们所求的 int-pairs。）

将序对的一般流称为 (pairs S T)，并将其分解为三部分：序对 (S₀, T₀)、第一行中其余的序对，以及剩余的序对：

(S₀, T₀) (S₀, T₁) (S₀, T₂) …

(S₁, T₁) (S₁, T₂) …

(S₂, T₂) …

…

注意，分解中的第三部分（不在第一行的序对）递归地就是由 (stream-cdr S) 和 (stream-cdr T) 形成的序对。另外注意，第二部分（第一行中其余的序对）为：

(stream-map (lambda (x)
(list (stream-car s) x))
(stream-cdr t))

因此，我们可以如下构造序对的流：

(define (pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(⟨combine-in-some-way⟩
(stream-map (lambda (x)
(list (stream-car s) x))
(stream-cdr t))
(pairs (stream-cdr s)
(stream-cdr t)))))

为完成这个过程，我们必须选择某种方式合并两个内部流。一种想法是使用类似 2.2.1 节 append 过程的流模拟：

(define (stream-append s1 s2)
(if (stream-null? s1)
s2
(cons-stream
(stream-car s1)
(stream-append (stream-cdr s1) s2))))

然而这对无穷流并不适用，因为它会在纳入第二个流之前先取完第一个流的所有元素。尤其是，若我们试图用以下方式生成所有正整数序对：

(pairs integers integers)

结果流会先尝试遍历第一个整数为 1 的所有序对，因而永远无法产生第一个整数取其他值的序对。

为处理无穷流，我们需要设计一种合并顺序，保证只要程序运行足够长的时间，每个元素最终都能被取到。一种优雅的做法是使用以下 interleave 过程：

(define (interleave s1 s2)
(if (stream-null? s1)
s2
(cons-stream
(stream-car s1)
(interleave s2 (stream-cdr s1)))))

由于 interleave 交替从两个流中取元素，即使第一个流是无穷的，第二个流的每个元素最终也都会进入交错流中。

这样，我们可以如下生成所求的序对流：

(define (pairs s t)
(cons-stream
(list (stream-car s) (stream-car t))
(interleave
(stream-map (lambda (x)
(list (stream-car s) x))
(stream-cdr t))
(pairs (stream-cdr s) (stream-cdr t)))))