オンラインSICP読書女子会 #7

[オンラインSICP読書女子会 #7 (1.3.1 ~ 1.3.2)](http://ladiespp.connpass.com/event/29144/)

前回: [オンラインSICP読書女子会 #6](http://ladiespp.connpass.com/event/28089/) (1.2.6, 練習問題1.25~1.29), [くーむ氏のまとめ](http://qiita.com/cocodrips/items/3ab87b16c341085da18d), [自分のまとめ](http://qiita.com/hio-harp/items/9955bf218c6c7de9193e)


## 1.3 高階手続きによる抽象の定式化

## 1.3.1 引数としての手続き

```scm
; [sec-1.3.1.scm]
(define (sec-1.3.1)
	(display "(sum-cubes 1 10) ==> ")
	(display (sum-cubes 1 10))
	(newline)
	(display "(sum-integers 1 10) ==> ")
	(display (sum-integers 1 10))
	(newline)
	(display "(* 8 (pi-sum 1 1000)) ==> ")
	(display (* 8 (pi-sum 1 1000)))
	(newline)
	(display "(integral cube 0 1 0.01) ==> ")
	(display (integral cube 0 1 0.001))
	(newline)
	(display "(integral cube 0 1 0.001) ==> ")
	(display (integral cube 0 1 0.0001))
	(newline)
	#t)


(define (sum term a next b)
	(if (> a b)
		0
		(+ (term a)
			(sum term (next a) next b))))


(define (cube a)
	(* a a a))


(define (inc n) (+ n 1))
(define (sum-cubes a b)
	(sum cube a inc b))


(define (identity x) x)
(define (sum-integers a b)
	(sum identity a inc b))


(define (pi-sum a b)
	(define (pi-term x)
		(/ 1.0 (* x (+ x 2))))
	(define (pi-next x)
		(+ x 4))
	(sum pi-term a pi-next b))


(define (integral f a b dx)
	(define (add-dx x)
		(+ x dx))
	(* (sum f (+ a (/ dx 2.0)) add-dx b)
		dx))
```

```scm
gosh> (sec-1.3.1)
(sum-cubes 1 10) ==> 3025
(sum-integers 1 10) ==> 55
(* 8 (pi-sum 1 1000)) ==> 3.139592655589783
(integral cube 0 1 0.01) ==> 0.249999875000001
(integral cube 0 1 0.001) ==> 0.24999999874993412
#t
```

### ex-1.29 シンプソンの公式を使った定積分

```scm
; [ex-1.29.scm]
(load "./sec-1.3.1")

(define (ex-1.29)
	(display (simpson's-rule cube 0 1 100))
	(newline)
	(display (simpson's-rule cube 0 1 1000))
	(newline)
	#t)

(define (simpson's-rule f a b n)
	(define h (/ (- b a) n))
	(define (y k)
		(f (+ a (* k h))))
	(define (my-term k)
		(cond
			((= k 0) (y k))
			((= k n) (y n))
			((odd? k) (* 4 (y k)))
			(else (* 2 (y k)))))
	(define my-sum
		(sum my-term 0 inc n))
	(/ (* h my-sum) 3))
```

```scm
gosh> (load "./ex-1.29")
#t
gosh> (ex-1.29)
1/4
1/4
#t
```

なぜかぴったり $\frac{1}{4}$ に・ω・；

### ex-1.30 線形反復による sum の再実装

```scm
; [ex-1.30.scm]
(load "./ex-1.29")

(define (ex-1.30)
	(ex-1.29))

(define (sum term a next b)
	(define (iter a result)
		; (display (list a result)) (newline)
		(if (> a b)
			result
			(iter (next a) (+ result (term a)))))
	(iter a 0))
```

```scm
gosh> (load "./ex-1.30")
#t
gosh> (ex-1.30)
1/4
1/4
#t
```

## ex-1.31 Π (product) の実装

### ex-1.31 (a) 線形反復での実装

```scm
; [ex-1.31-a.scm]
(load "./sec-1.3.1")

(define (ex-1.31-a)
	(display "10! = ")
	(display (factorial 10))
	(newline)
	(display "pi-product 1 1000 = ")
	(display (pi-product 1 1000))
	(newline)
	#t)


(define (product term a next b)
	(define (iter x result)
		(if (> x b )
			result
			(iter (next x) (* result (term x)))))
	(iter a 1.0))


(define (factorial n)
	(product identity 1 inc n))


(define (pi-product a b)
	(define (pi-term i)
		(define k (* i 2))
		(/ (* k (+ k 2))
			(square (+ k 1))))
	(* 4 (product pi-term a inc b)))
```

```scm
gosh> (load "./ex-1.31-a")
#t
gosh> (ex-1.31-a)
10! = 3628800.0
pi-product 1 1000 = 3.1423773650938855
#t
```

### ex-1.31 (b) 線形再帰での実装

```scm
; [ex-1.31-b.scm]
(load "./ex-1.31-a")

(define (ex-1.31-b)
	(ex-1.31-a))

(define (product term a next b)
	(if (> a b)
		1.0
		(* (term a)
			(product term (next a) next b))))
```

```scm
gosh> (load "./ex-1.31-b")
#t
gosh> (ex-1.31-b)
10! = 3628800.0
pi-product 1 1000 = 3.142377365093882
#t
```

## ex-1.32 集積関数 (accumulate)

### ex-1.32 (a) 反復再帰での実装

```scm
; [ex-1.32-a.scm]
(load "./ex-1.30")

(define (ex-1.32-a)
	(sec-1.3.1)
	(ex-1.30)
	#t)


(define (accumulate combiner null-value term a next b)
	(define (iter x result)
		(if (> x b )
			result
			(iter (next x) (combiner result (term x)))))
	(iter a null-value))

(define (sum term a next b)
	(accumulate + 0 term a next b))


(define (product term a next b)
	(accumulate * 1.0 term a next b))
```

```scm
gosh> (ex-1.32-a)
(sum-cubes 1 10) ==> 3025
(sum-integers 1 10) ==> 55
(* 8 (pi-sum 1 1000)) ==> 3.139592655589782
1/4
1/4
#t
```

### ex-1.32 (b) 線形再帰での実装

```scm
; [ex-1.32-b.scm]
(load "./ex-1.32-a")


(define (ex-1.32-b)
	(ex-1.32-a))


(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))))
```

```scm
gosh> (ex-1.32-b)
(sum-cubes 1 10) ==> 3025
(sum-integers 1 10) ==> 55
(* 8 (pi-sum 1 1000)) ==> 3.139592655589783
1/4
1/4
#t
```

## ex-1.33 filtered-accumulate

> a. *a* から *b* の区間の素数の二乗の和 (すでに `prime?` 述語を書いているとする)

> b. *n* と互いに素である *n* 未満のすべての正の整数 (つまり、 `gcd(i, n) = 1` となるすべての整数 `i < n`) の積


```scm
; [ex-1.33.scm]
(define (ex-1.33)
	(display "(ex-1.33-a 2 10) ==> ")
	(display (ex-1.33-a 2 10))
	(newline)
	(display "(ex-1.33-b 10) ==> ")
	(display (ex-1.33-b 10))
	(newline)
	#t)


(define (ex-1.33-a a b)
	(filtered-accumulate prime? + 0 cube a inc b))


(define (ex-1.33-b n)
	(define (relatively-prime-to-n? i)
		(= (gcd i n) 1))
	(filtered-accumulate relatively-prime-to-n? * 1.0 identity 1 inc (- n 1)))


(define (filtered-accumulate filter combiner null-value term a next b)
	(define (iter x result)
	(display (list x result))(newline)
		(if (> x b )
			result
			(iter (next x)
				(if (filter x)
					(combiner result (term x))
					result))))
	(display (list "enter: " filter combiner null-value term a next b))(newline)
	(iter a null-value))



(define (cube x) (* x x x))
(define (inc x) (+ x 1))
(define (identity x) x)


(define (gcd a b)
	(if (= b 0)
		a
		(gcd b (remainder a b))))


(define (smallest-divisor n)
	(find-divisor n 2))
(define (find-divisor n test-divisor)
	;(sys-nanosleep 1000000)
	;(display "!")
	(cond
		((> (square test-divisor) n)
			;(display "[prime:step:")
			;(display (- test-divisor 1))
			;(display "]")
			;(newline)
			n)
		((divides? test-divisor n)
			;(display "[div:step:")
			;(display (- test-divisor 1))
			;(display "]")
			;(newline)
			test-divisor)
		(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
	(= (remainder b a) 0))
(define (square a) (* a a))

(define (prime? n)
	(= n (smallest-divisor n)))
```

```scm
gosh> (ex-1.33)
(ex-1.33-a 2 10) ==> 503
(ex-1.33-b 10) ==> 189.0
#t
```

```
(a)
初期値 0
添字 2, 素数=yes, term=2*2*2=8,  result=8
添字 3, 素数=yes, term=3*3*3=27, result=35
添字 4, 素数=no
添字 5, 素数=yes, term=5*5*5=125, result=160
添字 6, 素数=no
添字 7, 素数=yes, term=7*7*7=343, result=503
添字 8, 素数=no
添字 9, 素数=no
添字 10, 素数=no
```

```
(b)
初期値 1
添字 1, 10と互いに素=yes, result=1*1=1
添字 2, 10と互いに素=no,
添字 3, 10と互いに素=yes, result=1*3=3
添字 4, 10と互いに素=no
添字 5, 10と互いに素=no
添字 6, 10と互いに素=no
添字 7, 10と互いに素=yes, result=3*7=21
添字 8, 10と互いに素=no
添字 9, 10と互いに素=yes, result=21*9=189
添字 10, 10と互いに素=no
```

## 1.3.2 `lambda` を使って手続きを構築する

`lambda` と `let` ようやくつかえる！・ヮ・*

## ex-1.34. `(f f)` の実行結果

予想:

```scm
(f f)
==> ; (define (f g) (g 2))
==> (f 2)
==> ; (define (f g) (g 2))
==> (2 2)
==> ;数値は演算子になれないのでエラー
```

実際:

```scm
; [ex-1.34.scm]
(define (ex-1.34)
	(f f))


(define (f g) (g 2))
```

```scm
gosh> (ex-1.34)
*** ERROR: invalid application: (2 2)
```