SICP: Exercise 1.33

問題 1.33

組み合せる項にフィルタ（filter）の考えを入れることで、accumulate（問題 1.32）の更に一般的なものが得られる。つまり範囲から得られて、指定した条件を満した項だけを組み合せる。出来上った filtered-accumulate 抽象は、accumulate と同じ引数の他、フィルタを指定する一引数の述語をとる。filtered-accumulate を手続きとして書け。filtered-accumulate を使い、次をどう表現するかを示せ。

区間 \( a \), \( b \) の素数の二乗の和（prime? 述語は持っていると仮定する。）

\( n \) と互いに素で、\( n \) より小さい正の整数（つまり \( i < n \) で \( \mathrm{GCD}(i, n) = 1 \) なる全整数 \( i \)）の積

「計算機プログラムの構造と解釈第二版 1.3.1 引数としての手続き」より

これもリストの扱いでよくありそうな処理、filter してから reduce。問題文にある通り、注目している番号が指定した条件を満たしているときのみ組合せを行うようにすればよい。

まずは再帰的プロセス版。

(define (filtered-accumulate combiner null-value pred term a next b)
  (if (> a b)
    null-value
    (if (pred a)
      (combiner (term a)
                (filtered-accumulate combiner
                                     null-value
                                     pred
                                     term
                                     (next a)
                                     next
                                     b))
      (filtered-accumulate combiner
                           null-value
                           pred
                           term
                           (next a)
                           next
                           b))))

続いて反復的プロセス版。こちらの方が簡潔に見える。

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

細かいことだけれど、引数の pred を入れる場所としてどこが最適かで悩んだ。この順番だと自然に読めるように感じたが、どうだろうか。

a

素数の 2 乗の和。filtered-accumulate のおかげでとても短く書ける。

(define (sum-of-squared-primes a b)
  (filtered-accumulate + 0 prime? square a inc b))

正しく答えが出れば prime? はどれでも良いので、1.2.6 節からどれかを持ってくる。ここでは本文と問題 1.23 のもので試してみる。

;; 反復的プロセスの filtered-accumulate
(define (filtered-accumulate combiner null-value pred term a next b)
  (define (iter a result)
    (if (> a b)
      result
      (iter (next a)
            (if (pred a)
              (combiner (term a) result)
              result))))
  (iter a null-value))

;; 素数判定
(define (prime? n)
  (= n (smallest-divisor n)))

(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 (next test-divisor)))))

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

(define (next n)
  (if (= n 2)
    3
    (+ n 2)))

;; 素数の 2 乗の和
(define (sum-of-squared-primes a b)
  (filtered-accumulate prime? + 0 square a inc b))

(define (square x) (* x x))

(define (inc x) (+ x 1))

;; 2 以上 10 以下の素数（2, 3, 5, 7）の 2 乗の和を求めてみる
(+ 4 9 25 49)
; => 87
(sum-of-squared-primes 2 10)
; => 87

合っていた。

b

\( n \) と互いに素で、\( n \) より小さい正の整数の積。一見ややこしい条件だけれど、互いに素（最大公約数が 1）かどうかを返す手続きを作れば分かりやすくなる。

(define (product-of-relatively-prime-numbers n)
  (define (relatively-prime? i) (= (gcd n i) 1))
  (filtered-accumulate * 1 relatively-prime? identity 1 inc (- n 1)))

こちらもテストしてみる。

;; 10 と互いに素で、それより小さい正の整数の積を求めてみる
(* 1 3 7 9)
; => 189
(product-of-relatively-prime-numbers 10)
; => 189

大丈夫だった。

抽象化のおかげで、いずれの場合も必要な部分だけ簡潔に書くことができた。無駄がなくてすっきり。

ochalog

RubyとMediaWikiとIRCが好き。

SICP: Exercise 1.33

問題 1.33

a

b