SICP exercise 3.67 - producing all pairs of integers without restrictions

Question

From SICP:

This is an infinite stream of ones:

 (define ones (cons-stream 1 ones))

This is an infinite stream of positive integers:

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

interleave takes elements alternately from two streams and returns the result

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

The following pairs procedure takes two streams s and t, and produces all pairs (s_i, t_j) such that 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)))))

So

 (pairs integers integers)

produces all pairs of integers i and j with i <= j.

Here is exercise 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.

My solution is:

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

So, I just changed (stream-cdr t) to t in the last recursive call. This appears to produce all pairs of integers.

What I don't understand is the statement:

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

What does this mean? Is my solution wrong? What do they mean when they say an additional stream?

Using my modified pairs2 procedure, these are the first 20 results:

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

It appears that your answer is indeed correct. For what is worth, I was able to solve it using one extra stream, which is what the authors meant with the hint "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))))))

My first 20 results are similar, although in some cases in different order or with different elements that will probably appear later on in your solution:

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