SICP 3.5.2 Infinite Streams - プログラミング再入門

ノート

必要になった部分の値をその時に生成する手法で無限リストが作れる。
以下の実装で

#lang racket
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
     (cons a (memo-proc (lambda () b))))))

(define stream-null? null?)
(define the-empty-stream null)

あとはテキストのままで

> (stream-ref no-sevens 100)
117
>

ちゃんと動く。

フィボナッチ数列の生成。fibgenは二つの引数を取り、ストリームを形成。最初の要素は最初の引数。次の要素は２番目の引数だがそれ以降のストリームを作る為にfibgenの第１引数として渡す。fibgenの第２引数は最初の第１引数と第２引数の和。

> (stream-ref fibs 0)
0
> (stream-ref fibs 1)
1
> (stream-ref fibs 2)
1
> (stream-ref fibs 3)
2
> (stream-ref fibs 6)
8
> (stream-ref fibs 10)
55
> 
>

エラストテネスの篩の実装。
2から始まる正の整数の数列から始めて、その先頭の要素と先頭の要素の倍数を取り除いた数列のリストと定義する。
2から辿って行くと、
（2 <2の倍数を除いた正の整数の数列（=先頭は3、数列Aとする）>）
（2 3 <数列Aから3の倍数を除いた正の整数の数列（=先頭は5、数列Bとする）>）
（2 3 5 <数列Bから5の倍数を除いた正の整数の数列（=先頭は7、数列Cとする）>）
…
と行った具合に順に素数を生成して行く事になる。

> (stream-ref primes 50)
233
>

ちゃんと動作している。

Defining streams implicitly

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

展開すると

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

要素を辿る度に(add-streams ones ...)が重なって行くのでintegersが返す先頭要素は常に１だが、それからadd-streamsの数だけ１が足された数がその要素の数となる。注釈にある通り3.50で作った複数の引数を取るstream-mapを用いて動かしてみる。

> (stream-ref integers 0)
1
> (stream-ref integers 10)
11
>

stream-refは0起点なので、結果の値とはひとつズレる。integersの定義の先頭要素を0にすれば一致する。

フィボナッチ数の場合は最初の二つの要素(0 1)が決まっていて、以降はこれを一つずらした数列を足して行くと定義出来る。

  (0) 1
      0 1
(0 1) 1←

から

  (0) 1 1←
      0 1 1←
(0 1) 1

  (0) 1 1
      0 1 1
(0 1) 1 2←

  (0) 1 1 2←
      0 1 1 2←
(0 1) 1 2

  (0) 1 1 2
      0 1 1 2
(0 1) 1 2 3←

  (0) 1 1 2 3←
      0 1 1 2 3←
(0 1) 1 2 3

  (0) 1 1 2 3
      0 1 1 2 3
(0 1) 1 2 3 5←

と成長して行く。

> (stream-ref fibs 0)
0
> (stream-ref fibs 1)
1
> (stream-ref fibs 2)
1
> (stream-ref fibs 3)
2
> (stream-ref fibs 4)
3
> (stream-ref fibs 5)
5
> (stream-ref fibs 6)
8
>

(define double (cons-stream 1 (scale-stream double 2)))

は(add-stream ones ...)の時と同様、２番目の要素には(double 2)が１回、３番目の要素には２回適用されるので、結果として2の0乗、1乗、2乗、3乗の数列となる。

> (stream-ref double 0)
1
> (stream-ref double 1)
2
> (stream-ref double 2)
4
> (stream-ref double 3)
8
>

prime?の判定は「√n以下の素数で割り切れるか否か」と言う定義を忠実にコードにしている。
ここではstream-filterが(integers-starting-from 3)が生成するリストを走査していく過程でprimeも成長して行く事で成り立っている。

n	primes	prime?	reason
3	(2)	true	2²>3
4	(2 3)	false	divisible by 2
5	(2 3)	true	3²>5
6	(2 3 5)	false	divisible by 2
7	(2 3 5)	true	3²>7
8	(2 3 5 7)	false	divisible by 2
9	(2 3 5 7)	false	divisible by 3
10	(2 3 5 7)	false	divisible by 2
11	(2 3 5 7)	true	5²>11

prime?は毎回primesを走査するが、どのnに対しても√n以上の素数が常にそれまでに見つかってprimesに足されていると言う条件が満たされるらしい。
動作確認。

> (stream-ref primes 0)
2
> (stream-ref primes 1)
3
> (stream-ref primes 2)
5
> (stream-ref primes 3)
7
> (stream-ref primes 4)
11
> (stream-ref primes 10)
31
> (stream-ref primes 100)
547
> (stream-ref primes 10000)
104743
>

Exercise 3.53

sの最初の要素は常に１なので、
1、1+1、(1+1)+(1+1)、{(1+1)+(1+1)}+{(1+1)+(1+1)} ...
と言う具合に増えて行く。a₀=1、a_n+1=a_n×2となる。
コードを実行するなと書いてあるが確かめてみると。

> (stream-ref s 0)
1
> (stream-ref s 1)
2
> (stream-ref s 2)
4
> (stream-ref s 3)
8
> (stream-ref s 4)
16
>

Exercise 3.54

問題文は0番目が1!、1番目が2!、2番目が3!との事。
$n! = n \times(n-1)!$ なので、factorialとintegersを掛ければ良い事は明白だが、単純に書くと1番目1、2番目が2、3番目が6と一つズレてしまう。なのでstream-cdrでintegersを一つ進めて

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

とする。

> (stream-ref factorials 0)
1
> (stream-ref factorials 1)
2
> (stream-ref factorials 2)
6
> (stream-ref factorials 3)
24
>

Exercise 3.55

簡単に書くと $\Sigma n = n + \Sigma n - 1$ なので

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

今回はずらさなくても良さそう。動作確認。

> (stream-ref (partial-sum integers) 0)
1
> (stream-ref (partial-sum integers) 1)
3
> (stream-ref (partial-sum integers) 2)
6
> (stream-ref (partial-sum integers) 3)
10
> (stream-ref (partial-sum integers) 4)
15
> (stream-ref (partial-sum integers) 5)
21
>

Exercise 3.56

2、3、5以外の素因数を持たない正の整数の列。つまり1で始まって2、3、5の倍数のみを含む数列と言う事。
ハミング数と言うらしい。
形としては1から始めて、各要素の2倍、3倍、5倍の数を片っ端からマージして行く。
マージは二つのストリームのcarを取って小さい方をconsの第１引数に、それ以外の要素をマージしたものを第２引数に構築して行く。
定義は文字通り、1で始まり、全ての2の倍数と3の倍数と5の倍数を昇順に並べた数列。

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

ストリームの先頭いくつかだけをリストにする関数を作って結果を調べる。

(define (stream->list s n)
  (if (= n 0)
      '()
      (cons (stream-car s) (stream->list (stream-cdr s) (- n 1)))))

実行結果

> (stream->list S 30)
'(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80)
>

Exercise 3.57

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

こちらのフィボナッチ数の定義で加算が行われる回数を数える。
fibsは(0 )で定義されていて、以降はstream-cdrで辿る時に評価して値に変わるがfibが指しているリストの内容が変わる訳ではないが、メモ化されている場合はローカル状態変数を持っていて、一度評価されるとこのローカル状態変数が次のconsペアを保持して評価された分だけ裏でfibsのリストを形成する。

メモ化されている場合は、足し算が行われてmemo-procの変数に格納されたらその要素を計算する為の足し算は二度と行われないので、一つの要素を作るのに１回の足し算、ただし最初の二つは足し算無しに生成される、またnは0から数える事を考慮するとn番目の要素を計算するのにn-1回の足し算が行われると言える。

メモ化されていない場合、add-streams計算過程で二つのfibsを辿るので、fib(n-1)とfib(n-2)までの足し算の回数の合計と最後に足し算が１回。これをstream-refが順に辿って行ってしまうので毎回の累計の回数の足し算が必要。

n	fib(n)の計算に必要な足し算の回数	fib(0)からfib(n)までの足し算の回数の累計
0	0回	0回
1	0回	0回
2	0+0+1=1回	1回
3	1+0+1=2回	3回
4	2+1+1=4回	7回
5	4+2+1=7回	14回
6	7+4+1=12回	26回
7	12+7+1=20回	46回
8	20+12+1=33回	79回
9	33+20+1=54回	133回

fib(n)を計算するのに必要な足し算の数をC_n=C_n-1+C_n-2+1とすると、上記のストリームで計算するには $\sum_{x=0}^{n}C_x$ 回の足し算を要する。

少し実験。stream-mapに渡す手続きを+ではなく自前の関数にして、呼び出される度に引数を表示する様にする。

(define (add a b) (display a)(display "+")(display b)(newline) (+ a b))
(define (add-streams s1 s2)
  (stream-map add s1 s2))

stream-refでフィボナッチ数を取り出す時に何回足し算が行われたかが分かる。stream-refは再帰的にstream-cdrを呼んで行くが、途中経過をdefineで取ってそれだけを評価すると、各stream-cdrの呼び出しで何回足し算が行われたかが分かる。

> (stream-ref fibs 0)
0
> (stream-ref fibs 1)
1
> (stream-ref fibs 2)
1+0
1
> (define fib1 (cdr fibs))
> fib1
#<procedure:...SICP Ex 3.57.rkt:5:13>
> (fib1)
'(1 . #<procedure:...SICP Ex 3.57.rkt:5:13>)
> (define fib2 (cdr (fib1)))
> fib2
#<procedure:...SICP Ex 3.57.rkt:5:13>
> (fib2)
1+0
'(1 . #<procedure:...SICP Ex 3.57.rkt:5:13>)
> (stream-ref fibs 3)
1+0
1+0
1+1
2
> (define fib3 (cdr (fib2)))
1+0
> (fib3)
1+0
1+1
'(2 . #<procedure:...SICP Ex 3.57.rkt:5:13>)
> (stream-ref fibs 4)
1+0
1+0
1+1
1+0
1+1
1+0
2+1
3
> (define fib4 (cdr (fib3)))
1+0
1+1
> (fib4)
1+0
1+1
1+0
2+1
'(3 . #<procedure:...SICP Ex 3.57.rkt:5:13>)
> (stream-ref fibs 5)
1+0
1+0
1+1
1+0
1+1
1+0
2+1
1+0
1+1
1+0
2+1
1+0
1+1
3+2
5
> (define fib5 (cdr (fib4)))
1+0
1+1
1+0
2+1
> (fib5)
1+0
1+1
1+0
2+1
1+0
1+1
3+2
'(5 . #<procedure:...SICP Ex 3.57.rkt:5:13>)
>

Exercise 3.58

割り算と言うより、num / denをradix進数で表した時の各桁の数字。
1/7=0.14285714285714

> (stream->list (expand 1 7 10) 10)
'(1 4 2 8 5 7 1 4 2 8)
>

3/8=0.375

> (stream->list (expand 3 8 10) 10)
'(3 7 5 0 0 0 0 0 0 0)
>

これなら2進数とか16進数も出来そう。

> (stream->list (expand 1 3 2) 10)
'(0 1 0 1 0 1 0 1 0 1)
> (stream->list (expand 1 4 2) 10)
'(0 1 0 0 0 0 0 0 0 0)
> (stream->list (expand 1 4 16) 10)
'(4 0 0 0 0 0 0 0 0 0)
>

Exercise 3.59

a.
$a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ...$
を積分すると
$c+a_0 x+\frac{1}{2}a_1 x^2+\frac{1}{3}a_2 x^3 + \frac{1}{4}a_3 x^4 + ...$
元の級数の係数の列を受け取って、それを積分した級数の係数の列（但し積分定数は除く）を返す。

(define (integrate-series s)
  (stream-map / s integers))

動作確認

> (stream->list (integrate-series (stream-enumerate-interval 1 10)) 10)
'(1 1 1 1 1 1 1 1 1 1)
> (stream->list (integrate-series ones) 10)
'(1 1/2 1/3 1/4 1/5 1/6 1/7 1/8 1/9 1/10)
>

b.
cosとsinは互いに微分した関係（積分にしても同じ）なので、互いに相手を用いて定義出来る筈。
cos xの係数を数列にすると
0, -1/2, 0, 1/(4×3×2),…
これを積分すると
0, -1/(3×2), 0, 1/(5×4×3×2),…

同様にsin xの係数を数列にすると
1, 0, -1(3×2), 0, 1/(5×4×3×2),…
これを積分すると
1/2, 0, -1/(4×3×2), 0, 1/(6×5×4×3×2),…

そうすると、
cos xはsin xを積分したものを符号反転して初項に0を加えたものと一致。
sin xはcos xを積分したものに初項1を加えたものと一致。

(define cosine-series
  (cons-stream 1 (scale-stream (integrate-series sine-series) -1)))

(define sine-series
  (cons-stream 0 (integrate-series cosine-series)))

実行結果

> (stream->list cosine-series 5)
'(1 0 -1/2 0 1/24)
> (stream->list sine-series 6)
'(0 1 0 -1/6 0 1/120)
>

定義と一致する。定数部分が今ひとつ腑に落ちないが
$cos x = 1 - \int sin x$
$sin x = \int cos x$
と言う事になる。

Exercise 3.60

冪級数の和はそれぞれの係数同士を足すだけなのでadd-streamsで実現出来る。
冪級数の積の係数は
$\sum_{k=0}^{n}a_n b_{n-k}$
で表されるが、ここでは単に多項式同士の掛け算を考える。
$(a_0 + a_1 x + a_2 x^2 + a_3 x^3 \dots)(b_0 + b_1 x + b_2 x^2 + b_3 x^3 \dots)$
ここから定数項、xの係数、x²の係数を順番に括り出す事を考える。
$=\{a_0 + (a_1 x + a_2 x^2 + a_3 x^3 \dots)\}\{b_0 + (b_1 x + b_2 x^2 + b_3 x^3 \dots)\}$
の４項の式と考えて、
$=a_0 b_0 + a_0(b_1 x + b_2 x^2 + b_3 x^3 \dots) + b_0(a_1 x + a_2 x^2 + a_3 x^3 \dots) + (a_1 x + a_2 x^2 + a_3 x^3 \dots)(b_1 x + b_2 x^2 + b_3 x^3 \dots)$
ここで
$a_0 b_0$ はただの掛け算。
$a_0(b_1 x + b_2 x^2 + b_3 x^3 \dots) + b_0(a_1 x + a_2 x^2 + a_3 x^3 \dots)$ はa₀とb₀でスケールしてからストリームの足し算。
$(a_1 x + a_2 x^2 + a_3 x^3 \dots)(b_1 x + b_2 x^2 + b_3 x^3 \dots)$ は字数が一つ上がった冪級数の掛け算。冪級数は係数でのも表しているので、これはmul-seriesで計算出来る。が他の項と足し算をするのに次数を合わせる必要があるので最初に0の項を足す。
以上を纏めると

(define (mul-series s1 s2)
  (cons-stream (* (stream-car s1) (stream-car s2))
               (add-streams (add-streams (scale-stream (stream-cdr s2)
                                                       (stream-car s1))
                                         (scale-stream (stream-cdr s1)
                                                       (stream-car s2)))
                            (cons-stream 0
                                         (mul-series (stream-cdr s1)
                                                     (stream-cdr s2))))))

動作確認

> (stream->list (add-streams (mul-series sine-series sine-series)
                             (mul-series cosine-series cosine-series)) 10)
'(1 0 0 0 0 0 0 0 0 0)
>

Exercise 3.61

定義のまま

(define (invert-unit-series s)
  (cons-stream 1
               (scale-stream (mul-series (stream-cdr s)
                                         (invert-unit-series s))
                             -1)))

検算。Sの定数項は1でなければならないので、sine-seriesでは検算出来ない。

> (stream->list (mul-series cosine-series
                            (invert-unit-series cosine-series)) 10)
'(1 0 0 0 0 0 0 0 0 0)
> (stream->list (mul-series exp-series
                            (invert-unit-series exp-series)) 10)
'(1 0 0 0 0 0 0 0 0 0)
>

Exercise 3.62

invert-unit-seriesの定義はSの定数項が1であることが前提。定数項が0でない任意の冪級数で割り算をする為には、それぞれの級数を分母側の級数の定数項で割って、分母となる級数の定数項を1に正規化すれば良さそう。

(define (div-series a b)
  (let ((b0 (stream-car b)))
  (if (= b0 0)
      (error "Divisor's constant term must not be zero")
      (let ((factor (/ 1 b0)))
        (mul-series (scale-stream a factor)
                    (invert-unit-series (scale-stream b factor)))))))

検算

> (stream->list (div-series sine-series cosine-series) 10)
'(0 1 0 1/3 0 2/15 0 17/315 0 62/2835)
> (stream->list (div-series (scale-stream sine-series 2) (scale-stream cosine-series 2)) 10)
'(0 1 0 1/3 0 2/15 0 17/315 0 62/2835)
> (stream->list (div-series cosine-series sine-series) 10)
. . Divisor's constant term must not be zero
>

定数項が1じゃなくても正しい答え。定数項が0ならエラー。