hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。
練習問題1.31
前回定義したsum手続きをちょっと改造して、積を返すようにしてみよう。
_.scm
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))
階乗を計算する手続きは、以下のように定義できる。
_.scm
(define (inc n) (+ n 1))
(define (identity x) x)
(define (factorial n) (product identity 1 inc n))
ところで、$\pi$の近似値は以下の式で得られる。
\frac{\pi}{4} = \frac{2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 ...}{3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7...}
作ってみよう。後で時間計測もしてみたいので、繰り返し回数を大きめにしてみる。
_.scm
(define (pi)
(define (term x)
(if (even? x) (/ (+ x 2.0) (+ x 1.0))
(/ (+ x 1.0) (+ x 2.0))))
(* (product term 1 inc 1000000) 4))
実行結果。
_.scm
gosh> (time (pi))
;(time (pi))
; real 0.841
; user 0.740
; sys 0.520
3.1415942243828017
続いて、反復プロセス版のproductを作ってみる。
_.scm
(define (product term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* (term a) result))))
(iter a 1))
pi手続きを再定義して実行してみよう。
_.scm
gosh> (time (pi))
;(time (pi))
; real 0.223
; user 0.220
; sys 0.000
3.141594224382854
練習問題 1.32
前回のsumは繰り返しのたびに和を、そしてさっきのproductは積を計算する手続きだったが、これを抽象化すればもっと一般的な集積関数を定義できる。
combinerとnull-valueという引数を新たに追加するのだ。
_.scm
(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a)
(accumulate combiner null-value term (next a) next b))))
このaccumulate手続きがあれば、sumやproductを簡単に定義しなおせる。
_.scm
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
反復プロセス版のaccumulateも定義してみよう。
_.scm
(define (accumulate combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner (term a) result))))
(iter a null-value))
練習問題 1.33
accumulate手続きにfilterを指定できるようにしよう。指定された条件をパスした値だけが集積されるようにするのだ。
_.scm
(define (filtered-accumulate filter combiner null-value term a next b)
(if (> a b)
null-value
(combiner (if (filter a) (term a) null-value)
(filtered-accumulate filter combiner null-value term (next a) next b))))
このfilterd-accumulate手続きを使って、指定された区間の素数の2乗の和を求めてみる。
だいぶ前に作成したprime?手続きを引っ張り出してこよう。
_.scm
(define (inc n) (+ n 1))
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divisor? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divisor? a b) (= (remainder b a) 0))
(define (prime? n)
(= n (smallest-divisor n)))
(define (sum-of-prime a b)
(filtered-accumulate prime? + 0 square a inc b))
実行結果。
_.scm
gosh> (sum-of-prime 1 10)
88 ; 1から10の間にある素数は1,2,3,5,7なので、1+4+9+25+49=88。
続いて、nと違いに素であるn未満の全ての整数の積、というのを求める。
「nと違いに素」とは、nとの最大公約数(GCD)が1になるということ。
だいぶ前に作ったGCD手続きを、また引っ張り出してこよう。
_.scm
(define (inc n) (+ n 1))
(define (identity x) x)
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
(define (product-of-coprime n)
(define (coprime? a)
(= (gcd n a) 1))
(filtered-accumulate coprime? * 1 identity 1 inc n))
実行結果。
_.scm
gosh> (product-of-coprime 10)
189 ; 1*3*7*9=189