SICPを読もう4 「1.3 高階手続きによる抽象」あたり

Programming Scheme SICP

問題1.14 - 1.28
気分転換したくなったのでパス！

問題1.29から1.33まで。高階手続きで抽象的に楽しもうというあたりで楽しもうと思います。
問題1.29

(define (cube x) (* x x x))
(define (simpson f a b n)
  (define h (/ (- b a) n))
  (define (iter k s)
    (if (= k n)
      (+ s (f b))
      (iter (+ k 1) (+ s (* (+ 2 (* 2 (modulo k 2))) (f (+ a (* k h))))))))
  (if (= (modulo n 2) 0) (* (/ h 3) (iter 1 (f a))) #f))
(simpson cube 0 1 100)
; 0.25000000000000006
(simpson cube 0 1 1000)
; 0.25000000000000006
(simpson cube 0 1 10000)
; 0.2500000000000001
(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))
(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2)) add-dx b)
     dx))
(integral cube 0 1 0.01)
; 0.24998750000000042
(integral cube 0 1 0.001)
; 0.249999875000001

integralおせー、とsumを反復プロセスに書き換えてみる。

(define (sum term a next b)
  (define (iter a+ s)
    (if (> a+ b) s (iter (next a+) (+ s (term a+)))))
  (iter a 0))
(integral cube 0 1 0.01)
; 0.24998750000000042
(integral cube 0 1 0.001)
; 0.24999987500000073

何この微妙な違い！ 気にせず進むけど！

問題1.30
あ、反復sumはこの問題で求められてたのか。1.29参照。
(iter a+ s)とかやってるけど、別にiterの中で元のaとか使ってないんでaにして束縛しちゃってもかまいません。別にわざわざ同じにしなくてもいいと思うけど。

問題1.31

(define (inc n) (+ n 1))
(define (product term a next b)
  (define (iter a+ s)
    (if (> a+ b) s (iter (next a+) (* s (term a+)))))
  (iter a 1))
(define (f n) (/ (+ 2 (* 2 (quotient n 2))) (+ 1 (* 2 (quotient (+ n 1) 2)))))
(f 1)
; 0.6666666666666666
(f 3)
; 0.8
(* 4 (product f 1 inc 10000))
; 3.1417497057380084
(* 4 (product f 1 inc 100000))
;3.141608361277941
(* 4 (product f 1 inc 1000000))
; 3.141594224382854

反復的プロセスにて。うーんあんましよくもないかなあ。

再帰プロセスだと

(define (product term a next b)
  (if (> a b) 1 (* (term a) (product term (next a) next b))))
(* 4 (product f 1 inc 10000))
; 3.1417497057379635
(* 4 (product f 1 inc 100000))
; 3.1416083612780903
(* 4 (product f 1 inc 1000000))
; 3.1415942243828017

なんかたいして速さ変わらんな。別のところで時間食ってるのか。あー、速い速くねえとかの話題が飛ばした箇所に含まれてたな。

問題1.32
めんどくさいのでコードだけ。
再帰プロセス

(define (accumlate combiner null-value term a next b)
  (if (> a b) null-value (combiner (term a) (accumlate combiner null-value term (next a) next b))))
(define (product term a next b)
  (accumlate * 1 term a next b))
(* 4 (product f 1 inc 1000000))
; 3.1415942243828017

反復プロセス

(define (accumlate combiner null-value term a next b)
  (define (iter a+ s)
    (if (> a+ b) s (iter (next a+) (combiner s (term a+)))))
  (iter a null-value))
accumlate
(* 4 (product f 1 inc 1000000))
; 3.141594224382854

問題1.33

(define (filterd-accumlate filter? combiner null-value term a next b)
  (define (iter a+ s)
    (if (> a+ b)
      s
      (if (filter? a+)
        (iter (next a+) (combiner s (term a+)))
        (iter (next a+) s))))
  (iter a null-value))
(define (true n) #t)
(define (product term a next b)
  (filterd-accumlate true * 1 term a next b))
(* 4 (product f 1 inc 1000000))
; 3.141594224382854

こんな感じで。

(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))
(define (prime? n)
  (= n (smallest-divisor n)))
(define (square x) (* x x))
(filterd-accumlate prime? + 0 square 0 inc 10)
; 88
(+ 1 4 9 25 49)
; 88
((lambda (a b) (filterd-accumlate prime? + 0 square a inc b)) 0 10)
; 88

素数の二乗の和が出てますね。ちょっと先取りしてlambda式形式で書くとこういうことで。

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))
((lambda (n) (filterd-accumlate (lambda (a+) (= (gcd a+ n) 1)) * 1 (lambda (a+) a+) 1 (lambda (a+) (+ a+ 1)) n)) 5)
; 24
((lambda (n) (filterd-accumlate (lambda (a+) (= (gcd a+ n) 1)) * 1 (lambda (a+) a+) 1 (lambda (a+) (+ a+ 1)) n)) 10)
; 189

もう次の項からlambdaなんだからちょっとフライングでlambdalambdaしてしまえ。

test