SICP読書録 #11 練習問題1.31 - 練習問題1.33

[hiroshi-manabe様の日本語訳](https://github.com/hiroshi-manabe/sicp-pdf)を使わせてもらいます。
練習問題等は[Gauche](http://practical-scheme.net/gauche/index-j.html)で実行。

[前回はこちら](https://qiita.com/shuetsu@github/items/52e83dbf63894d28f94e)

### 練習問題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$の近似値は以下の式で得られる。

```math
\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
```