第8回SICP勉強会
今回は採用活動のお手伝いで大阪出張のため、勉強会本編には参加できず。
今回で一章が終わりだったので、参加できずに残念。
1.3.4 値として返される手続き
- 手続きを値として返すことができるという話
- Newton法
- 抽象と第一級手続き
問題
問題1.40
;; 問題1.40 (define (newton-transform g) (lambda (x) (- x (/ (g x) ((deriv g) x))))) (define (newtons-method g guess) (fixed-point (newton-transform g) guess)) (define (cubic a b c) (lambda (x) (+ (* x x x) (* a x x) (* b x) c))) ;; x^3 - x = 0 ;; => x(x^2 -1) = 0 ;; => x = 0, 1, -1 (newtons-method (cubic 0 -1 0) 2.0) ;; gosh> 1.0000000000000002 (newtons-method (cubic 0 -1 0) -2.0) ;; gosh> -1.0000000000000002
問題1.41
;; 問題1.41 ;; 引数として一引数の手続きをとり、 ;; 受け取った手続きを二回作用させる ;; 手続きを返す手続きdoubleの実装 (define (double f) (lambda (x) (f (f x)))) (define (inc x) (+ x 1)) ((double inc) 1) ;; gosh> 3 ;; (double inc) ;; => (lambda (x) (inc (inc x))) (((double (double double)) inc) 5) ;; gosh> 21
問題1.42
;; 問題1.42 ;; 一引数の関数fとgを用いて ;; gの後のfの合成関数を定義する (define (compose f g) (lambda (x) (f (g x)))) (define (inc x) (+ x 1)) (define (square x) (* x x)) ((compose square inc) 6) ;; (* (+ 6 1) (+ 6 1)) ;; gosh> 49
問題1.43
;; 問題1.43 ;; fをn回作用させる手続き (define (compose f g) (lambda (x) (f (g x)))) (define (repeated f n) (define (iter i g) (if (= i n) g (iter (+ i 1) (compose f g)))) (iter 1 f)) (define (square x) (* x x)) (define (inc x) (+ x 1)) ((repeated square 2) 5) ;; gosh> 625 ((repeated inc 10) 5) ;; gosh> 15
問題1.44
;; 問題1.44 ;; n重平滑化関数の手続き (define (compose f g) (lambda (x) (f (g x)))) (define (repeated f n) (define (iter i g) (if (= i n) g (iter (+ i 1) (compose f g)))) (iter 1 f)) (define (smooth f) (define dx 0.00001) (lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3))) (define (n-fold-smooth f n) (repeated (smooth f) n))
問題1.45
;; 問題1.45 ;; n乗根をm回の平均緩和を使って解いて収束を見る実験 (define (n-fold-average-damp n) (repeated average-damp n)) (define (n-root-exp n x m) (fixed-point ((n-fold-average-damp m) (lambda (y) (/ x (expt y (- n 1))))) 1.0)) (n-root-exp 2 2 0) ;; ☓ (n-root-exp 2 2 1) (n-root-exp 3 2 1) (n-root-exp 4 2 1) ;; ☓ (n-root-exp 4 2 2) (n-root-exp 5 2 2) (n-root-exp 6 2 2) (n-root-exp 7 2 2) (n-root-exp 8 2 2) ;; ☓ (n-root-exp 8 2 3) ;; ここから、必要なm回は、n = 2^iとしたときの、 ;; i以下の最も大きな整数 ;; と推測できる (define (n-root n x) (define (damp-count m) (if (< m 2) 0 (+ 1 (damp-count (/ m 2))))) (fixed-point ((n-fold-average-dump (damp-count n)) (lambda (y) (/ x (expt y (- n 1)))))))
問題1.46
;; 問題1.46 (define (iterative-improve good-enough? improve) (define (check guess) (let ((next-guess (improve guess))) (if (good-enough? guess next-guess) next-guess (check next-guess)))) (lambda (initial-guess) (check initial-guess))) (define (average x y) (/ (+ x y) 2)) (define (square x) (* x x)) ;; sqrtの手続き (define (sqrt x) (define (good-enough? guess next-guess) (< (abs (- (square next-guess) x)) 0.001)) (define (improve guess) (average guess (/ x guess))) ((iterative-improve good-enough? improve) x)) (sqrt 9.0) ;; gosh> 3.00009155413138 ;; fixed-pointの手続き (define tolerance 0.00001) (define (fixed-point f first-guess) (define (close-enough? guess next-guess) (< (abs (- guess next-guess)) tolerance)) (define (improve guess) (f guess)) ((iterative-improve close-enough? improve) first-guess)) (define (average-damp f) (lambda (x) (average x (f x)))) (define (fixed-point-sqrt x) (fixed-point (average-damp (lambda (y) (/ x y))) 1.0)) (fixed-point-sqrt 9.0) ;; gosh> 3.0
所感
- 出張とかあって、時間が全然足りなかったので、最後の方は相当あやしい
- 2章も引き続きゆるゆると頑張ります