@uents blog

Code wins arguments.

SICP 読書ノート#36 - 3.5.2 無限ストリーム(1) (pp.193-196)

SICP Scheme

“To inifity and beyond”

トイ・ストーリーでのBuzz Lightyearの決め台詞です。

無限ストリーム(infinite streams)を極めると、さらにその先の世界が見えるかもしれない :)

トイ・ストーリー MovieNEX [ブルーレイ+DVD+デジタルコピー(クラウド対応)+MovieNEXワールド] [Blu-ray]

トイ・ストーリー MovieNEX [ブルーレイ+DVD+デジタルコピー(クラウド対応)+MovieNEXワールド] [Blu-ray]

無限ストリームとは

無限に1が続くonesというストリームは以下のように定義できる。

(define ones
  (cons-stream 1 ones))

至ってシンプル。今の僕ではこんなの逆立ちしても思いつかない…

実際に操作してみる。stream->listは永遠に評価し続けるので返ってこない。

racket@> (time (stream-ref ones 0))
cpu time: 0 real time: 0 gc time: 0
1
racket@> (time (stream-ref ones 1))
cpu time: 0 real time: 0 gc time: 0
1
racket@> (time (stream-ref ones 10000))
cpu time: 3 real time: 3 gc time: 0
1
racket@> (time (stream-ref ones 1000000))
cpu time: 211 real time: 210 gc time: 0
1
racket@> (stream->list ones)
=> 返ってこない

実際にどう評価されているかを頭で追ってみると、

(stream-ref ones 100)
=> (stream-ref (cons-stream 1 ones) 100)
=> (stream-ref (stream-cdr ones) 99)
=> (stream-ref ones 99)
=> (stream-ref (stream-cdr ones) 98)
=> (stream-ref ones 98)
...
=> (stream-ref ones 1)
=> (stream-ref (stream-cdr ones) 0)
=> (stream-ref ones 0)
=> (stream-car ones)
=> 1

よくよくみるとこれって、

  • \( o_{0} = 1 \)
  • \( o_{1} = o_{0} \)
  • \( o_{2} = o_{1} \)
  • ...
  • \( o_{k} = o_{k - 1} \)

の要素を持つ数列 \( \{o_{n}\} = \{1, 2, \dots, o_{k}, \dots \} \) と同じである。要は(define ones ...)というのは、初項 \( 1 \) で一般項 \( o_{k} = o_{k - 1} \) を持つ数列と等価であり、この数列の表現をSchemeの並びとして実装したとも言える。

さらに、 \( \{o_{n}\} \) の \( k \) 番目からの部分列を \( \{o_{n(k)}\} \) のように表記すると、

\( \{o_{n}\} = \{1, \{o_{n(1)}\}\} = \{1, \{1, \{o_{n(2)}\}\}\} = \dots = \{1, \{1, \dots \{1, \{o_{n(k)}\}\}\}\} \)

と定義できる。なので、(stream-ref <stream> k)は<stream>の部分列をk回分剥がした結果を取り出しているとも言える。

次にintergersについて考える。

(define integers
  (cons-stream 1 (add-streams ones integers)))

これも数列として捉えると、

  • \( i_{0} = 1 \)
  • \( i_{1} = o_{0} + i_{0} = 2 \)
  • \( i_{2} = o_{1} + i_{1} = 3 \)
  • ...
  • \( i_{k} = o_{k - 1} + i_{k - 1} = k + 1 \)

となるので、

\( \{i_{n}\} = \{1, \{ o_{n(0)} + i_{n(0)} \} \} = \{1, \{ o_{0} + i_{0}, \{ o_{n(1)} + i_{n(1)} \} \} \} = \{1, \{ o_{0} + i_{0}, \dots \{ o_{k - 1} + i_{k - 1}, \{ o_{n(k)} + i_{n(k)} \} \} \} \} \)

と定義できる。

逆に数列として明示的に定義されれば、無限ストリームで実装可能である。

例えばフィボナッチ数の場合、

  • \( f_{0} = 0 \)
  • \( f_{1} = 1 \)
  • \( f_{2} = f_{1} + f_{0} \)
  • ...
  • \( f_{k} = f_{k - 1} + f_{k - 2} \)

なので、

(define fib
  (cons-stream 0
               (cons-stream 1
                            (add-streams
                             fibs
                             (stream-cdr fibs)))))

と定義通りに実装すればよい。

無限ストリームを生成する手続きを実装することもできる。

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

これを使って素数の無限ストリームを生成する。

(define primes
  (cons-stream
   2
   (stream-filter prime? (integers-starting-from 3))))

テスト。

racket@> (map (lambda (i) (stream-ref primes i))
              (enumerate-interval 0 10))
=> '(2 3 5 7 11 13 17 19 23 29 31)

おもしろい。

練習問題

問題 3.53

以下のストリームの要素について説明せよ。

(define s (cons-stream 1 (add-streams s s)))

数列の定義から考える。

  • \( a_{0} = 1 \)
  • \( a_{1} = a_{0} + a_{0} = 2 \)
  • \( a_{2} = a_{1} + a_{1} = 4 \)
  • \( a_{3} = a_{2} + a_{2} = 8 \)
  • ...
  • \( a_{k} = a_{k - 1} + a_{k - 1} = 2^k \)

テスト。定義通り。

racket@> (map (lambda (i) (stream-ref s i))
              (enumerate-interval 0 10))
=> '(1 2 4 8 16 32 64 128 256 512 1024)

問題 3.54

mul-streamは素直に実装すればよい。

(define (mul-stream s1 s2)
  (stream-map * s1 s2))

階乗の数列は以下のように定義される。

  • \( f_{0} = 1 \)
  • \( f_{1} = 1 * f_{0} \)
  • \( f_{2} = 2 * f_{1} \)
  • \( f_{3} = 3 * f_{2} \)
  • ...
  • \( f_{k} = k * f_{k - 1} \)

定義通りに実装すればよいので、

(define factorials
  (cons-stream 1 (mul-streams integers factorials)))

テスト。

racket@> (map (lambda (i) (stream-ref factorials i))
              (enumerate-interval 0 10))
=> '(1 1 2 6 24 120 720 5040 40320 362880 3628800)

問題 3.55

partial-sumsの各項は以下の通りになるので、

  • \( p_{0} = s_{0} \)
  • \( p_{1} = s_{0} + s_{1} = p_{0} + s_{1} \)
  • \( p_{2} = s_{0} + s_{1} + s_{2} = p_{1} + s_{1} \)
  • ...
  • \( p_{k} = s_{0} + \dots + s_{k - 1} = p_{k - 1} + s_{k - 1} \)

これもまた定義通りに実装する。

(define (partial-sums s)
  (cons-stream (stream-car s)
               (add-streams (partial-sums s) (stream-cdr s))))

テスト。

racket@> (map (lambda (i) (stream-ref (partial-sums integers) i))
              (enumerate-interval 0 10))
=> '(1 3 6 10 15 21 28 36 45 55 66)

OK。だいぶつかめてきた。

問題 3.56

1と2、3、5の倍数の並びを作る。

mergeを組み合わせることに気づくのにすごい時間がかかったorz

(define S
  (cons-stream 1
               (merge (scale-stream S 2)
                      (merge (scale-stream S 3) (scale-stream S 5)))))

テスト。

racket@> (map (lambda (i) (stream-ref S i))
              (enumerate-interval 0 20))
=> '(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40)

問題 3.57

どこでやらなかったっけ？既視感がすごいあるが。

メモ化されている場合は、n回の加算で済む。

メモ化されていない場合は、

  • fib_{n} + fib_{n-1}を求めるには、fib_{n-1} + fib_{n-2}とfib_{n-1} + fib_{n-2}の加算が必要で、
  • fib_{n-1} + fib_{n-2}を求めるには、fib_{n-2} + fib_{n-3}とfib_{n-3} + fib_{n-4}の加算が必要で、
  • ...

といった具合で指数的に増加する。

問題 3.58

まずは脳内で解いてみる。

    (expand 3 4 10)
=> '(7 (expand 2 5 10))
=> '(7 (5 (expand 0 5 10)))
=> '(7 (5 (0 (expand 0 5 10))))
=> '(7 (5 (0 (0 (expand 0 5 10)))))
=> '(7 (5 (0 (0 (0 ... (expand 0 5 10))))))

となるので、radixを基数とした除算結果をストリームで返す手続き。

テスト。expandという名前はRacketの組み込みマクロと重複するようなので、別の名前で実装。

(define (my-expand num den radix)
  (cons-stream
   (quotient (* num radix) den)
   (my-expand (remainder (* num radix) den) den radix)))

;; test
racket@> (map (lambda (i) (stream-ref (my-expand 3 4 10) i))
              (enumerate-interval 0 10))
=> '(7 5 0 0 0 0 0 0 0 0 0)

racket@> (map (lambda (i) (stream-ref (my-expand 4 3 10) i))
              (enumerate-interval 0 10))
=> '(13 3 3 3 3 3 3 3 3 3 3)

全体のソースコードはGitHubに置いています。

次回は「§3.5.2 無限ストリーム」の練習問題の続きから。

※「SICP読書ノート」の目次はこちら