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：

练习3.67：修改pairs程序，使(pairs integers integers)产生所有整数对(i, j)的流（没有条件(i <= j)）。提示：您需要混合使用其他流。

我的解决方案是：

(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。这似乎产生了所有整数对。

我不明白的是声明：

提示：您需要混合使用其他流。

这是什么意思？我的解决方案有误吗？当他们说一个额外的流时他们是什么意思？

使用我修改过的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)