読者です 読者をやめる 読者になる 読者になる

@uents blog

Code wins arguments.

SICP 読書ノート#37 - 3.5.2 無限ストリーム(2) (pp.196-197)

SICP Scheme

問題 3.59

べき級数、聞き覚えはあるから習ったことはあるんだろうけど、さっぱり思い出せない。こんな時はWikipedia。先生いつもありがとう。

(a)

べき級数の項のストリームを引数に取り、それを積分した結果の項のストリームを返すintegrate-seriesを実装する。

引数のストリームを \( \{s_{n}\} \) とすると、

  • \( i_{0} = s_{0} \)
  • \( i_{1} = \frac{1}{2} s_{1} \)
  • \( i_{2} = \frac{1}{3} s_{2} \)
  • \( i_{3} = \frac{1}{4} s_{3} \)
  • ...
  • \( i_{k} = \frac{1}{k} s_{k} \)

のようなストリームを返す手続きを実装すればよいので、

(define (integrate-series s)
  (define (iter s k)
    (cons-stream (/ (stream-car s) k)
                 (iter (stream-cdr s) (+ k 1))))
  (iter s 1))

テスト。

racket@> (define i (integrate-series ones))
racket@> (map (lambda (x) (stream-ref i x))
              (enumerate-interval 0 5))
=> '(1 1/2 1/3 1/4 1/5 1/6)

(b)

まずはexp-seriesを動かしてみる。

(define exp-series
  (cons-stream 1 (integrate-series exp-series)))

;; test
racket@> (map (lambda (x) (stream-ref exp-series x))
              (enumerate-interval 0 5))
=> '(1 1 1/2 1/6 1/24 1/120)

確かに、

\( e^{x} = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots \)

の定義通り \( k \) 番目の項が \( \frac{1}{k!} \) となっている。うーん、すごい。

次にcos、sinの級数の式について、

\( \cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \dots \)

\( \sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \dots \)

それぞれ積分してみると、

\( \int \cos x = x - \frac{x^3}{3!} + \frac{5^4}{5!} - \dots = \sin x \)

\( \int \sin x = \frac{x^2}{2!} - \frac{x^4}{4!} + \frac{x^6}{6!} - \dots = 1 - \cos x \)

より、

\( \cos x = 1 - \int \sin x \)

\( \sin x = \int \cos x \)

となるので、この定義をそのまま実装する。

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

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

テスト。元々のべき級数の式と同じになる。

racket@> (map (lambda (i) (stream-ref cosine-series i))
              (enumerate-interval 0 10))
=> '(1 0 -1/2 0 1/24 0 -1/720 0 1/40320 0 -1/3628800)

racket@> (map (lambda (i) (stream-ref sine-series i))
              (enumerate-interval 0 10))
=> '(0 1 0 -1/6 0 1/120 0 -1/5040 0 1/362880 0)

問題 3.60

2つのべき級数の項のストリームをそれぞれ \( \{ a_{n} \} \) 、\( \{ b_{n} \} \) とすると、2つのべき級数の積の項のストリームは、

  • \( m_{0} = a_{0} * b_{0} \)
  • \( m_{1} = a_{0} * b_{1} + a_{1} * b_{0} \)
  • \( m_{2} = a_{0} * b_{2} + a_{1} * b_{1} + a_{2} * b_{0} \)
  • \( m_{3} = a_{0} * b_{3} + a_{1} * b_{2} + a_{2} * b_{1} + a_{3} * b_{0} \)
  • ...

となる。

問題の穴埋めについて

(define (mul-series s1 s2)
  (cons-stream ⟨??⟩ (add-streams ⟨??⟩ ⟨??⟩)))

\( m_{0} \) より最初の<??>は自明。

(* (stream-car s1) (stream-car s2))

2、3番目の<??>add-streamsの引数となるので、

(add-streams <??> (mul-series <??> <??>))

のように畳み込みながら足すイメージなんだけど、全然思いつかず…

1〜2日寝かせて、図を凝視していたら分かった。

  • \( m_{0} = a_{0} * b_{0} \)
  • \( m_{1} = a_{0} * b_{1} + a_{1} * b_{0} \)
  • \( m_{2} = a_{0} * b_{2} + a_{1} * b_{1} + a_{2} * b_{0} \)
  • \( m_{3} = a_{0} * b_{3} + a_{1} * b_{2} + a_{2} * b_{1} + a_{3} * b_{0} \)
  • ...
  • \( m = a_{0} * \{ b_{n} \} + a_{1} * \{ b_{n} \} + a_{2} * \{ b_{n} \} + a_{3} * \{ b_{n} \} + \dots \)

上の図の通りに実装。

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

テスト。

racket@> (map (lambda (i) (stream-ref (mul-series integers integers) i))
              (enumerate-interval 0 5))
=> '(1 4 10 20 35 56)

キタ━(゚∀゚)━!

問題 3.61-62

問題3.60と同様、ほとんど数学なのでパス。

次回は「§3.5.3 ストリームパラダイムの開発」から。


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