問題3-66〜68

｢対の無限のストリーム｣というトピックで、任意の対を無限に並べたように見えるストリームを扱います。
問題3-66。本文に掲載されているpairsの動きを調べます。(pairs integers integers)がどのようなストリームになっているのかを100個くらい出力し、その規則性を紙に書き出してみました。(i, j)の対を生成する訳ですが、iの方向へはかなり早く広がっていき、jの方向へはinterleaveの影響があるためゆっくりと広がっていきます。iとjがnで等しいとき、それが出現する順番は、(1, 3, 7, 15, 31, 63, 127)になっていたので、初項が1で、公差が2の(n-1)乗の等差数列です。だから、対(100, 100)はおそろしく後方に位置していることになります。また、それぞれのiを一つずつ増やした対(n, (n+1))は、(n, n)が出現する順番よりも、2の(n-1)乗だけ後方になります。それ以降、(n, (n+2))、(n, (n+3))は等間隔で現れ、その間隔は、2のn乗になっています。そのため、対(1, 100)は198番目に出現するのではないかと考えられます。
問題3-67。対の片方よりも大きいような組み合わせではなく、全ての組み合わせを生成するストリームを定義します。対角線上に位置する対を除いて、(i, j)を生成する時に、(j, i)も生成してinterleaveすればよさそうです。

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

(define all-int-pairs (all-pairs integers integers))

;=>(1 1)
;=>(1 2)
;=>(2 2)
;=>(2 1)
;=>(2 3)
;=>(1 3)
;=>(3 3)
;=>(3 1)	
;=>...

問題3-68。Louisの実装だと、無限ループが発生してしまいます。原因としては、pairs内のinterleaveで第二引数にpairsを渡していますが、この時点でpairsはcons-streamが一回もされておらず、stream-car/stream-cdrをするための要素が定義されていません。だから、interleaveのs2を扱う際に、値を確定できずに処理が止まらなくなってしまうのではと考えられます。