SICP 练习 3.67 - 无限制地生成所有整数对

Question

来自 SICP：

这是无穷无尽的：

 (define ones (cons-stream 1 ones))

这是正整数的无限流：

 ; add-streams takes two streams and produces a stream of their elementwise sum
 (define integers (cons-stream 1 (add-streams ones integers)))

interleave 交替从两个流中获取元素，returns 结果

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

以下 pairs 过程采用两个流 s 和 t，并生成所有对 (s_i, t_j)，使得 i <= j.

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

所以

 (pairs integers integers)

生成所有整数对 i 和 j 以及 i <= j.

这是练习 3.67：

Exercise 3.67: Modify the pairs procedure so that (pairs integers integers) will produce the stream of all pairs of integers (i, j) (without the condition (i <= j)). Hint: You will need to mix in an additional stream.

我的解决方案是：

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

所以，我只是在最后一次递归调用中将(stream-cdr t)更改为t。这似乎会产生所有整数对。

我不明白的是声明：

Hint: You will need to mix in an additional stream.

这是什么意思？我的解决方案错了吗？当他们说额外的流时，他们是什么意思？

使用我修改后的 pairs2 程序，这些是前 20 个结果：

> (define p2 (pairs2 integers integers))
> (stream-ref p2 0)
(1 1)
> (stream-ref p2 1)
(1 2)
> (stream-ref p2 2)
(2 1)
> (stream-ref p2 3)
(1 3)
> (stream-ref p2 4)
(2 2)
> (stream-ref p2 5)
(1 4)
> (stream-ref p2 6)
(3 1)
> (stream-ref p2 7)
(1 5)
> (stream-ref p2 8)
(2 3)
> (stream-ref p2 9)
(1 6)
> (stream-ref p2 10)
(3 2)
> (stream-ref p2 11)
(1 7)
> (stream-ref p2 12)
(2 4)
> (stream-ref p2 13)
(1 8)
> (stream-ref p2 14)
(4 1)
> (stream-ref p2 15)
(1 9)
> (stream-ref p2 16)
(2 5)
> (stream-ref p2 17)
(1 10)
> (stream-ref p2 18)
(3 3)
> (stream-ref p2 19)
(1 11)

Answer 1

看来你的回答确实是正确的。值得一提的是，我能够使用一个额外的流来解决它，这就是作者在提示 "You will need to mix in an additional stream":

中的意思

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

我的前 20 个结果是相似的，尽管在某些情况下顺序不同或具有不同的元素，这些元素稍后可能会出现在您的解决方案中：

(1 1)
(1 2)
(2 1)
(1 3)
(2 2)
(1 4)
(3 1)
(1 5)
(2 3)
(1 6)
(4 1)
(1 7)
(3 2)
(1 8)
(5 1)
(1 9)
(2 4)
(1 10)
(6 1)
(1 11)

SICP 练习 3.67 - 无限制地生成所有整数对

SICP exercise 3.67 - producing all pairs of integers without restrictions

lisp

scheme

stream

sicp

infinite