SICP 読み (5)

scheme SICP

問題 1.33 が終わったら 1.3.2 節以降なんですが、数学なナニばっかりだなぁ。ま、コンピュータってのは基本的に「計算機」なんでそうなるのは仕方ないよなぁ。って今頃何言ってるんだろうか。(駄目

問題 1.33 (filterd-accumulate)

なかなか興味深い問題。filtered-accumulate はどちらが望ましいのだろうか。

その 1

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

その 2

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

これは置き換えなナニで最適な方を選択するべきなんだろうか。正規順序だとその 1 はあり得んだろうな。
あら、よく見てみるとその 1 は filter にヒッカからなくて stack 突き破る可能性があるな。

その 3 (その 1 改)

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

うーん ... 微妙。
とりあえず、以下なナニでは動作している模様。

(define (aa a b)
  (filtered-accumulate (lambda (x) #t)
		       (lambda (x y) (+ x y))
		       0
		       (lambda (x) x)
		       a
		       (lambda (x) (+ x 1))
		       b))

試験なソレを書く癖も付けといた方が良いな。

guile> (define (test-aa)
  (eq? 55 (aa 1 10)))
guile> (test-aa)
#t
guile>

TDD な道具が作れんかなぁ。ま、いいや。
a. については prime? 作るのが面倒なので上記 aa で OK としときます。一応ダミーな prime? で、な解を以下に。

(define (prime? x) #t)
(define (aa a b)
  (filtered-accumulate prime?
		       (lambda (x y) (+ x y))
		       0
		       (lambda (x) x)
		       a
		       (lambda (x) (+ x 1))
		       b))
(define (test-aa) (eq? 55 (aa 1 10)))

次は b. です。
GCD なソレは 27p のものを流用。

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

条件は以下ですか。

  • i は i < n な整数
  • GCD(i, n) = 1
  • 上記の条件を満たす数列の積

1 から 10 までで考えると 10 と素な数列の積は (* 1 3 7 9) なので試験な手続きを含めた一連の手続きは以下。

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

(define (bb a b)
  (filtered-accumulate (lambda (x) (eq? 1 (gcd b x)))
		       (lambda (x y) (* x y))
		       1
		       (lambda (x) x)
		       a
		       (lambda (x) (+ x 1))
		       b))

(define (test-bb)
  (eq? (* 1 3 7 9) (bb 1 10)))

試験を。

guile> (test-bb)
#t
guile>

なんか出力になーんの色気もないなぁ。
んーと、上記手続きは a < b 前提で作ってあるんですがセーフかなぁ。微妙だなぁ。