問題 3-66 (3.5.3 Exploiting the Stream Paradigm)

integers ってのは自然数の無限リストです．

(dump-stream integers 10)
; 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, done

今，pairs って関数がある． $S,T$ という無限ストリームを引数にとって pairs が作るのは，次のようなストリームです．
$\{(s,t)|s\leq t, s\in S, t\in T\}$
ちなみに定義は以下のようになっている．

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

(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) によって生成されるストリームのうち， (1, 100) や (99, 100)，(100, 100) は何番目の要素になるでしょうって問題です．

この問題のキーになるのは，関数 interleave．定義を見れば分かるように，s1，s2 の要素が先頭から交互に並ぶストリームを返してくれる．実例を見ると分かりやすい．

(dump-stream (interleave integers (stream-map (lambda (x) (+ x 100)) integers)) 10)
; 1, 101, 2, 102, 3, 103, 4, 104, 5, 105, done

というわけで段々分かってきた!

(1, x) というペアに関しては，(pairs integers integers) で生成されるペアの無限ストリームで (1,1) が一番最初に出てきた後，一つ飛ばしに出現するようになります．結果として， $x \ne 1$ となる x について，(1, x) の要素番号は， $2x-2$ となっていることが分かります．結果，(1, 100) の要素番号は [2\times 100-2=198] で 198 番目の要素となります．stream-ref は最初の要素番号が 0 であることを考慮すると，