理系学生日記

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

忍者TOOLS

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

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

って結果.

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

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

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