理系学生日記

おまえはいつまで学生気分なのか

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

SICP

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 であることを考慮すると，

(stream-ref result 197) ; (1 100)

って結果．

あー一般化しようとするとなんかかなりの漸化式になりそうだし，

But feel free to give more qualitative answers if you find yourself getting bogged down.

ってことだからもうここで stop しとく．