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