今回のあらすじ
SICP の 3.5.2 Infinite Streams をサクサク読んで、Execise 3.55 まで解きます。
3.5.2 Infinite Streams
無限の長さをもつストリームについて
ストリームは、stream-cdrで実際にアクセスしようとした分だけ評価されます(もちろんstream-mapのような内部でstream-cdrを呼んでいる処理も同様です)。この特徴を利用すれば、無限の長さをもつシーケンスを表すことができます。
このような無限の長さをもつストリームのすべての要素を評価することはできませんが、一部分を評価して値を取得したりすることはできます。
ストリームの暗黙的定義について
ストリームの定義の方法には明示的に生成する方法と暗黙的に生成する方法があります。前者は (define integers (integers-starting-from 1)) のようにストリームを生成する手続きを明示的に呼び出す方法です。後者はストリームが遅延評価されるという性質を利用して、自分の最初の要素を利用して次の要素を生成していく方法です。
Exercise 3.53.
Without running the program, describe the elements of the stream defined by
(define s (cons-stream 1 (add-streams s s)))
手続きsは暗黙的に定義されています。順をおってs要素を考えると、
最初の要素は1。
2番目の要素は(add-streams s s)の最初の要素になります。sの最初の要素が1なので、(add-streams s s)の最初の要素は2。
3番目の要素は(add-streams s s)の2番目の要素になります。 sの2番目の要素が2なので、4。
以下同様なので、sは最初の要素が1でn番目の要素が2^(n-1)になります。
Exercise 3.54.
Define a procedure mul-streams, analogous to add-streams, that produces the elementwise product of its two input streams. Use this together with the stream of integers to complete the following definition of the stream whose nth element (counting from 0) is n + 1 factorial:
(define factorials (cons-stream 1 (mul-streams <??> <??>)))
mul-streamsの定義はストリームを2つ受け取り、それぞれのn番目の要素を掛け合わせたストリームを返すものなので以下のように定義できます。
(define (mul-streams s1 s2)
(stream-map * s1 s2))factorialsは1, 2, 6, 24...という要素をもつストリーム。問題の定義を見ると最初の要素はすでにできているので、2番目以降の要素を(mul-streams <??> <??>で作りたいです。以下のように定義できます。
(define factorials
(cons-stream 1 (mul-streams
factorials
(stream-cdr integers))))factorialsの要素を順をおって調べてみます。factorialsのn番目の要素が評価されたタイミングでそれぞれの値がどうなっているか表にして見ていきましょう。
最初の要素は1。
|-------------|------------|-----------------------|------------------------------------------------|
| n番目の要素 | factorials | (stream-cdr integers) | (mul-streams factorials (stream-cdr integers)) |
|-------------|------------|-----------------------|------------------------------------------------|
| 1 | 1 | 未評価 | 未評価 |
|-------------|------------|-----------------------|------------------------------------------------|
2番目の要素は(mul-streams factorials (stream-cdr integers)の最初の要素なので(* (stream-car factorials) (stream-car (stream-cdr integers))です。factorialsの最初の要素が1なので、結果は2となります。
|-------------|------------|-----------------------|------------------------------------------------|
| n番目の要素 | factorials | (stream-cdr integers) | (mul-streams factorials (stream-cdr integers)) |
|-------------|------------|-----------------------|------------------------------------------------|
| 1 | 1 | 2 | 2 |
| 2 | 2 | 未評価 | 未評価 |
|-------------|------------|-----------------------|------------------------------------------------|
3番目の要素は(mul-streams factorials (stream-cdr integers)の2番目の要素なので(* <factoirialsの2番目の要素> <(stream-cdr integers)の2番目の要素>です。factorialsの2番目の要素が2なので、結果は6となります。
|-------------|------------|-----------------------|------------------------------------------------|
| n番目の要素 | factorials | (stream-cdr integers) | (mul-streams factorials (stream-cdr integers)) |
|-------------|------------|-----------------------|------------------------------------------------|
| 1 | 1 | 2 | 2 |
| 2 | 2 | 3 | 6 |
| 3 | 6 | 未評価 | 未評価 |
|-------------|------------|-----------------------|------------------------------------------------|
4番目の要素は(mul-streams factorials (stream-cdr integers)の3番目の要素なので(* <factorialsの3番目の要素> <(stream-cdr integers)の3番目の要素>です。factorialsの3番目の要素が6なので、結果は24となります。
|-------------|------------|-----------------------|------------------------------------------------|
| n番目の要素 | factorials | (stream-cdr integers) | (mul-streams factorials (stream-cdr integers)) |
|-------------|------------|-----------------------|------------------------------------------------|
| 1 | 1 | 2 | 2 |
| 2 | 2 | 3 | 6 |
| 3 | 6 | 4 | 24 |
| 4 | 24 | 未評価 | 未評価 |
|-------------|------------|-----------------------|------------------------------------------------|
上記の通り、(mul-streams factorials (stream-cdr integers)のn番目の値が(* <n-1の階乗> n) という形で作られていくことがわかります。
Exercise 3.55.
Define a procedure partial-sums that takes as argument a stream S and returns the stream whose elements are
S0, S0 + S1, S0 + S1 + S2, ....For example,(partial-sums integers)should be the stream1, 3, 6, 10, 15, ....
3.55 も 3.54 と同じ要領解くことができます。partial-sumsの2番目以降の要素をn+1番目の要素(nは1以上)とすると、n+1番目の要素はn番目の要素+引数のストリームSのn+1番目の要素と表すことができます。また、partial-sumsの1番目の要素はSの1番目の要素です。
なのでpartial-sumsは以下のように定義できます。
(define (partial-sums S)
(cons-stream (stream-car S)
(add-streams (partial-sums S)
(stream-cdr S))))上記のコードは間違ってませんが、いちいちpartial-sumsを呼び出すのでパフォーマンスが悪いです。メモ化が行われるように修正すると以下のようになります。
(define (partial-sums S)
(define p-sums
(cons-stream (stream-car S)
(add-streams p-sums
(stream-cdr S))))
p-sums)次回予告
Execise 3.56 から Execise 3.58 までを解きます。
＃人気の記事
＃タグ
