ぱいそんにっき

The limits of my language are the limits of my world.

計算機プログラムの構造と解釈と闘う:: 対の無限ストリーム編(前)[3.66-3.68]

無限が無限に続くなんて妄想だった

間が空きましたが続きを読んで行きましょう(^^) [1] 遅延評価, とっても興味深いです. プログラミングは SF だったんだとわくわくしながら読んでいます.

数は無限に存在する...それは本当に? 今まで無限というのは終わりのない永遠さだと思っていました. しかし, 無限には終わりがあるのでしょう. なぜならストリームは無限を入れ子にすことができるから. 今後記述する “無限” とは永遠性の意味はこめられていませんのでご注意を.

では続き. \(i ≤ j\)\(i + j\) が素数であるすべての整数 \((i, j)\) の対のストリームを例に教科書が再開しました.

(stream-filter
  (lambda (pair)
    (prime? (+ (car pair) (cadr pair))))
  int-pairs)

int-pairs (整数のペア) を取り出して, その和が素数からなる数列ですね.

この節では “対” の作り方を学んでいくみたいです. 順不同の整数の対が全通り入った int-pairs を作るをどう作るか考えていきます.

2 つのストリームのそれぞれの項の値を組み合わせて対を作っていくのですが, 順不同の対を作りたいので下の表のように, 整数のストリーム s と t を組み合わせた全ての場合を網羅する数列になればいいみたいですね.

\((s_0, t_0)\) \((s_0, t_1)\) \((s_0, t_2)\) \((s_0, t_3)\) ...
  \((s_1, t_1)\) \((s_1, t_2)\) \((s_1, t_3)\) ...
    \((s_2, t_2)\) \((s_2, t_3)\) ...
      \((s_3, t_3)\) ...

この表を示すような対のストリーム \((pairs \s \t)\) を数列, そして S 式をどう表現しましょう... とおろおろしていましたが, SICP 先生はすごすぎでした. 解説を聞いて学んでいきます.

上の表を以下のように区分してみましょう.

\((s_0, t_0)\) \((s_0, t_1)\) \((s_0, t_2)\) \((s_0, t_3)\) ...
  \((s_1, t_1)\) \((s_1, t_2)\) \((s_1, t_3)\) ...

rst で上手く表を書けなかったのですが, (pairs s t) は

  1. 第 1 行 1 列目: \((s_0, t_0)\)
  2. 第 1 行の残りの対: \((s_0, t_j)\)
  3. 残りの対: \((s_i, t_j)\)

と裂いてみます. このとき 2. と 3. の数列を interleave という手続きを作ってそれを組み合わせることで全てのペアを作れるそうです. どう頭をひねってもこんな素晴らしい発想出てこない(涙)

(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(s,t) = (s_0, interleave(s_0\times t(1), pairs(s(1), t(1))))\)

第 0 項, 第 1 項, 第 2 項 を順に書き出してみます.

第 0 項

\(pairs(s,t)_0 = (s_0, t_0)\)

第 1 項

\(pairs(s,t)_1 = interleave(s_0 \times t(1), pairs(s(1), t(1)))_0\)
\(pairs(s,t)_1 = ((s_0 \times t(1))_0, interleave(pairs(s(1), t(1)), s_0\times t(2)))_0\)
\(pairs(s,t)_1 = (s_0 \times t(1))_0\)
\(pairs(s,t)_1 = (s_0,t(1))_0\)
\(pairs(s,t)_1 = (s_0, t_1)\)

第 2 項

\(pairs(s,t)_2 = interleave(pairs(s(1), t(1)), s_0 \times t(2))_0\)
\(pairs(s,t)_2 = (pairs(s(1), t(1))_0, interleave(s_0\times t(2), pairs(s(1), t(1))(1)))_0\)
\(pairs(s,t)_2 = pairs(s(1), t(1))_0\)
\(pairs(s,t)_2 = (s(1),t(1))_0\)
\(pairs(s,t)_2 = (s_1, t_1)\)

よくみると, pairs の第 1 項以降は \(s_0 \times t(n)\)\(pairs(s(1),t(1))_n\) を交互に繰り返しています.

  1. 第 1 行 1 列目: \((s_0, t_0)\) すなわち \((s_0, t_0)\)
  2. 第 1 行の残りの対: \((s_0, t_j)\) すなわち \(s_0 \times t(n)\)
  3. 残りの対: \((s_i, t_j)\) すなわち \(pairs(s(1),t(1))_n\)

となりそうです. ここから練習問題を解いていきます. むずかしい...

続きを解いていく

ex-3.66

(pairs integers integers) を調べよ. 対がストリームに置かれる順につき, 一般的に述べることが出来るか. 例えば対 (1, 100), 対 (99, 100), 対 (100, 100) の前に近似的に何個の対が来るか.

ほい. 半年前の自分の記事を読み返しながらもう一度考えていきます(・.・) [2] 上の続きを考えていきます.

2. の場合を展開すると,

\(s_0 \times t(n)=(s_0,\times t(1),\ s_0,\times t(2),\ s_0,\times t(3)...\ s_0,\times t(j))\)

となります. 2. の場合は 1. の場合の数 1 を足し, 更に 3. と交互に出てくることを考えて, この j 番目の \(s_0 \times t(n)\) というのは \(2(j-1)+1\) 番目, つまり \(2j+1\) 番目に相当します.

ここで 3. の場合を考えるために \(i, j\) を満たすペアが paris ストリームに出てくるのを \(n\) 番目をしたときの \(index\) という数列があると考えます. 3. の場合は, \((s_i,\ t_j)\)\(index(i, j)\) 番目にいるときに 1 行 1 列分ずれているので \(index(i-1,j-1)\) 番目にいると言えます. よって, 3. の \(pairs(s(1),t(1))_n\) は全体の数列から見たら \(2*index(i-1,j-1)+2\) 番目に相当すると考えられます. (2 を足しているのは 1. の分と, 2. の第 1 項の分)

ここから 3. の一般項を求めるために index を求めます. \(index(i,j)\) のときに \(2*index(i-1,j-1)+2\) となるので, この 2 つは同値といえます.

\(index(i,j) = 2*index(i-1,j-1)+2\)

飛ばし気味でしょうか. ここで一旦 S 式に置き換えて考えてみましょう(さらなる混乱のもとかも?)

(define (index i j)
  (cond
    ((or (< i 0) (< j 0) (> i j)) -1) ; 表に無い座標のとき
    ((and (= i 0) (= j 0)) 0) ; 1. の場合
    ((and (= i 0) (> j 0)) (- (* 2 j) 1)) ; 2. の場合
    (else
      (+ (* 2 (index (- i 1) (- j 1))) 2)))) ; 3. の場合

(index i j) の返す値が n と想定しています. 都合の良いように適時 S 式と数列を切り替えて考えています. さぁ, 3. に相当する else の場合を見てみましょう.

漸化式になっている?! さっき書いた \(index(i,j) = 2*index(i-1,j-1)+2\) が見て分かりますね. 漸化式とわかれば一般項を求めるまでです.

\(index_{i, j}=2*index_{i-1, j-1}+2\) を解く前に, ここでちょっと脱線. ある数列 \(a_{i}=b\times a_{i-1}+c\) の一般項は

\(a_{i}+\frac{c}{b-1}=b\times a_{i-1}+c+\frac{c}{b-1}\)
\(a_{i}+\frac{c}{b-1}=b^i\times (a_{0}+\frac{c}{b-1})\)

と導きだされます.

この定理を用いて求めたい式を展開していきます.

\(index_{i,\ j}=2index_{i-1,\ j-1}+2\)
\(index_{i,\ j}+2=2(index_{i-1,\ j-1}+2)+2\)
\(index_{i,\ j}=2^i(a_{0}+2)-2\)

ここで \(index_{i,\ j}\) の第 0 項の \(index_{0}\) を求めましょう. 以下, \(k=j-i\) とおきます.

\(a_{i}=index_{i,i+k}\)
\(a_{i}+2=2(a_{i-1}+2)\)
\(a_{i}=2^i(a_{0}+2)-2\)

よって

\(index_{i,i+k}=2^i(a_{0,k}+2)-2\)
\(index_{i,j}=2^i(a_{0,j-i}+2)-2\)

一般項は

\(index_{i,j}=2^i(a_{0,j-i}+2)-2\)

となります. ... これが一般項?! 美しすぎですよまったく.... j=i の時の \(index_{i,j}\)\(2^i(a_{0,0}+2)-2=2^i(0+2)-2=2^{i+1}-2\) となるので, これを整理して S 式に適応してみます.

(define (index i j)
  (if (= i j)
      (- (expt 2 (+ i 1)) 2)
      (- (* (expt 2 i) (+ (* 2 (- j i)) 1)) 2)))

めちゃシンプルに美しくなった?! 感動!!!

では問題の解答. (1, 100), (99, 100), (100, 100) の前に近似的に何個の対が来るか, つまりこれらが第何項に相当するか求めるのですね. index 手続きにそのまま適応すると, (index 1, 100), (index 99, 100), (index 100, 100) の出力結果はそれぞれ

(index 1 100)   ; 396
(index 99 100)  ; 1901475900342344102245054808062
(index 100 100) ; 2535301200456458802993406410750

となりました! この出力結果が, 解答の項になりますね.

数学難しかったのですが問題を解いてくださり解法を教えてくださった @cocoatomo さん, 本当にありがとうございます(^^) 自力では到底解けませんでした. 大感謝です!!!

ex-3.67

pairs 手続きを修正し, (pairs integers integers) が (i ≤ j の条件なしに) 整数のすべての対 (i, j) のストリームを生じるようにせよ.

分からなかったので解答を見ながら理解を試みます.

(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
      (interleave
        (stream-map
          (lambda (x) (list (stream-car s) x))
           (stream-cdr t))
        (stream-map
          (lambda (x) (list (stream-car t) x))
           (stream-cdr s)))
      (pairs (stream-cdr s) (stream-cdr t)))))
\((s_0, t_0)\) \((s_0, t_1)\) \((s_0, t_2)\) \((s_0, t_3)\) ...
\((s_1, t_0)\) \((s_1, t_1)\) \((s_1, t_2)\) \((s_1, t_3)\) ...

4 つに区切り, 左上, 右上, 左下, 右下の順に

  1. \((s_0, t_0)\)
  2. \(s_0 \times t(n)\)
  3. \(pairs(s(1),t(1))_n\)
  4. \(t_0 \times s(n)\)

となるのでしょう.

数列に置き換えて tex で書くのに疲れてきたので(なまけもの), ここからは “イメージ” で書いておきます.

((1. の部分), interleave(interleave(2. の部分 と 3. の部分) と 4. の部分)) ってなんとなくイメージできた. 2. と 3. に吸い込まれて平面上に広がって行く感じ.

ex-3.68

Louis Reasoner は対のストリームを三つの部分から作るのは必要以上に複雑だと考えた. 対(S0, T0)を第一行の残りの対から分離する代り, 次のようにして第一行全体を使うことを提案した: これは動くか. Louis の pairs の定義を使って (pairs integers integers) を評価すると, 何が起きるか考えよ.
(define (pairs s t)
  (interleave
    (stream-map
      (lambda (x) (list (stream-car s) x))
      t)
    (pairs (stream-cdr s) (stream-cdr t))))

数列に置き換えて考えましょう.

\(pairs(s,t) = interleave(s_0\times t, pairs(s(1), t(1)))\)

展開してみます.

\(pairs(s,t) = interleave(s_0 \times t, pairs(s(1), t(1)))\)
\(pairs(s,t) = ((s_0 \times t)_0, interleave(pairs(s(1), t(1)), s_0\times t(1)))\)
\(pairs(s,t) = ((s_0 \times t)_0, pairs(s(1), t(1))_0, interleave(s_0\times t(1)), pairs(s(1), t(1))(1)))\)

\((s_0 \times t)_0\) が値でなくストリーム(t の項は無限に続く)として返ってきまうので, 実行すると処理が無限に続いてしまいますね.

きりが悪いけど一旦休憩

ここらで休憩します. 残りの 3.69 ~ 3.72 は次回に.

もっと思考の持久力を付けねば...(;;)

無限には永遠性がないことがわかったけど, 思考はそうであって欲しくないなぁと思いながら続けていきます. 宇宙が有限ならば !有限 は !宇宙? !宇宙が例えば想像力とか夢だったらどうかな..とかとか.