SICP問題3.67

pairs手続きを修正して(pairs i j)が(i<=jの条件なしに)整数全ての対(i,j)のストリームを生じるように修正する。
元のpairs手続き

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

ここで生成している並びは

(list (stream-car s) (stream-car t))
=> (1, 1) (2, 2) (3, 3) ...
(stream-map (lambda (x) (list (stream-car s) x))
            (stream-cdr t))
=> (1, 2) (1, 3) (1, 4) ... (2, 3) (2, 4) ... (3, 4) (3, 5) ...

であり、ここで足りないのは i < j のストリーム

(2, 1) (3, 1) (3, 2) (4, 1) ...

で、これは一つ前のストリームの逆となるので

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

をinterleaveを使って混ぜればよい。
ということで修正後のpairs手続き

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

テスト

(stream-ref-range (pairs integers integers) 0 50)
; (1 1)
; (1 2)
; (2 2)
; (2 1)
; (2 3)
; (1 3)
; (3 3)
; (3 1)
; (3 2)
; (1 4)
; (3 4)
; (4 1)
; (2 4)
; (1 5)
; (4 4)
; (5 1)
; (4 2)
; (1 6)
; (4 3)
; (6 1)
; (2 5)
; (1 7)
; (4 5)
; (7 1)
; (5 2)
; (1 8)
; (3 5)
; (8 1)
; (2 6)
; (1 9)
; (5 5)
; (9 1)
; (6 2)
; (1 10)
; (5 3)
; (10 1)
; (2 7)
; (1 11)
; (5 4)
; (11 1)
; (7 2)
; (1 12)
; (3 6)
; (12 1)
; (2 8)
; (1 13)
; (5 6)
; (13 1)
; (8 2)
; (1 14)

OK