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

オンラインSICP読書女子会 #7 (1.3.1 ~ 1.3.2)

前回: オンラインSICP読書女子会 #6 (1.2.6, 練習問題1.25~1.29), くーむ氏のまとめ, 自分のまとめ

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

1.3.1 引数としての手続き

; [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))

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 シンプソンの公式を使った定積分

; [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))

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

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

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

; [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))

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

ex-1.31 Π (product) の実装

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

; [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)))

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) 線形再帰での実装

; [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))))

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) 反復再帰での実装

; [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))

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) 線形再帰での実装

; [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))))

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) の積

; [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)))

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) の実行結果

予想:

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

実際:

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


(define (f g) (g 2))

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