stream - 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从两个流中交替取元素并返回结果

(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

看来你的回答确实是正确的。值得一提的是，我能够使用一个额外的流来解决它，这就是作者在提示“您需要混合一个额外的流”时的意思:

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