[SICP] 問題 1.33 : filtered-accumulate

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

a. 区間a, bの素数の二乗の和(prime?述語は持っていると仮定する.)
b. nと互いに素で, nより小さい正の整数(つまりi < nでGCD(i, n)=1なる全整数i)の積

フィルターに対応したaccumulateを定義します. 考え方としては, filterが真を返すときはaccumulateと同様の処理をし, 偽を返すときはcombinerを使った計算をしないようにします. 手続きは次のようになります.

(require (lib "racket/trace.ss"))

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

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

(define (cube x) (* x x x))

(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 (smallest-divisor n)
  (find-divisor n 2))

(define (prime? n)
  (= n (smallest-divisor n)))

;; 再帰的プロセスを生成する.
(define (filtered-accumulate-r filter combiner null-value term a next b)
  (cond ((> a b) 
         null-value)
        ((filter a)
         (combiner (term a)
                   (filtered-accumulate-r filter combiner null-value term (next a) next b)))
        (else
         (filtered-accumulate-r filter combiner null-value term (next a) next b))))

;; 反復的プロセスを生成する.
(define (filtered-accumulate-i filter combiner null-value term a next b)
  (define (iter a result)
    (cond ((> a b) 
           result)
          ((filter a) 
           (iter (next a) (combiner (term a) result)))
          (else
           (iter (next a) result))))
  (iter a null-value))

;; 区間a, bの素数の二乗の和
(define (sum-prime-square a b)
  (filtered-accumulate-r prime?
                         +
                         0
                         square
                         a
                         inc 
                         b))

;; nと互いに素で, nより小さい正の整数の積
(define (product-disjoint n)
  (define (disjoint? x) (= 1 (gcd n x)))
  (filtered-accumulate-r disjoint?
                         *
                         1
                         identity
                         1
                         inc
                         (- n 1)))

区間a, bの素数の二乗の和を求めてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (sum-prime-square 2 10)   
87
> (+ (square 2) (square 3) (square 5) (square 7))
87
> 

2から10の間の素数は, 2, 3, 5, 7ですから, 計算は合っています.

nと互いに素で, nより小さい正の整数の積を求めてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (product-disjoint 10)
189
> (* 1 3 7 9)
189
> 

10よりも小さい正の整数で10と互いに素になる数は, 1, 3, 7, 9ですから, 計算は合っています.