SICP勉強会#4に参加しています

http://groups.google.co.jp/group/sicp-in-kansai/web/sicp-4
ごぶさたしています。久し振りにコンピュータ関係の集いに参加しています。

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

(define (cube n)
  (* n n n))

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

(integral cube 0 1 0.01)
; gosh> 0.24998750000000042
(integral cube 0 1 0.001)
; gosh> 0.249999875000001

(define (simpson f a b n)
  (define h
    (/ (- b a) n))
  (define (y k)
    (f (+ a (* k h))))
  (define (term i)
    (+ (y (- (* 2 i) 2))
       (* 4 (y (- (* 2 i) 1)))
       (y (* 2 i))))
  (define (next i)
    (+ i 1))
  (/ (* h (sum term 1 next (/ n 2))) 3))

(simpson cube 0.0 1 100)
; gosh> 0.2500000000000001
(simpson cube 0.0 1 1000)
; gosh> 0.25000000000000017

(define (simpson2 f a b n)
  (define h
    (/ (- b a) n))
  (define (x i)
    (+ a (* i h)))
  (define (next i)
    (+ i 1))
  (define (sum1)
    (* 2
       (sum (lambda (j) (f (x (* j 2))))
	    1
	    next
	    (- (/ n 2) 1))))
  (define (sum2)
    (* 4
       (sum (lambda (j) (f (x (- (* j 2) 1))))
	    1
	    next
	    (/ n 2))))
  (/ (* h (+ (f a) (sum1) (sum2) (f b))) 3))

(simpson2 cube 0.0 1 100)
; gosh> 0.25000000000000006
(simpson2 cube 0.0 1 1000)
; gosh> 0.2500000000000002
  • 1.30は普通に末尾再帰にするだけ。のはず。
(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
	 (sum term (next a) next b))))

(define (sum2 term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (+ result (term a)))))
  (iter a 0))

(define (id n) n)

(sum id 1 (lambda (i) (+ i 1)) 10)
(sum2 id 1 (lambda (i) (+ i 1)) 10)

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
	 (product term (next a) next b))))

(define (product2 term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (* result (term a)))))
  (iter a 1))

(define (id n) n)
(define (inc i) (+ i 1))

(product id 1 inc 4)
(product2 id 1 inc 4)

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

(define (pai n)
  (define (term i)
    (/ (* i (+ i 2.0)) (square (+ i 1.0))))
  (define (next i)
    (+ i 2.0))
  (define (square x) (* x x))
  (* 4.0 (product term 2 next n)))

(pai 1000) ; gosh> 3.1431607055322752
  • 1.32。らぶらぶinjectに誘導されている気がします。
(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
	result
	(iter (next a) (combiner result (term a)))))
  (iter a null-value))

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

(define (product term a next b)
  (accumulate * 1 term a next b))

(define (id n) n)
(define (inc i) (+ i 1))

(sum id 1 inc 10)
; gosh> 55
(product id 1 inc 10)
; gosh> 3628800
  • 1.33。prime?とかgcdは過去問から。
(define (square x) (* x x))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (divides? a b)
  (= (remainder b a) 0))

(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 (prime? n)
  (= n (smallest-divisor n)))

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

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

(define (inc i) (+ i 1))
(define (id n) n)

(define (f1 a b)
  (filtered-accumulate prime? + 0 square a inc b))

(f1 0 5) ; 1 + 4 + 9 + 25
; gosh> 39

(define (f2 a b)
  (define (gcd a b)
    (if (= b 0)
	a
	(gcd b (remainder a b))))
  (define (filter x)
    (= (gcd x b) 1))
  (filtered-accumulate filter * 1 id a inc b))

(f2 1 10) ; 1 * 3 * 7 * 9
; gosh> 189
  • 1.34。やっとlambdaがでてきました。
(define (square x) (* x x))

(define (f g)
  (g 2))

(f square)

(f (lambda (z) (* z (+ z 1))))

(f f)
;  -> (f 2)
;  -> (2 2)
gosh> *** ERROR: invalid application: (2 2)
Stack Trace: