計算機プログラムの構造と解釈 第二版 P34 問題1.33

方針は以下のような感じ


以下みたいな感じで、filterというパラメータを最後につける。

(filtered-accumulate combiner null-value term a next b filter)


そんで、この条件だったら、combinerパラメータで引き込んだ、関数やら「+」やら「-」
やらをやってやればいいので、それを行う部分で、filterの条件で分岐してやればいい。
だのでaccumulateを改造してこんな感じになる

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


問題aはprime?があれば、余裕。


問題bの所でつまずいた。

b. nと互いに素で、nより小さい正の整数(つまり1

全く意味がわかりません。


「互いに素」でゴーグルを調べてみます。
Wikipedia 互いに素
http://ja.wikipedia.org/wiki/%E4%BA%92%E3%81%84%E3%81%AB%E7%B4%A0

2数が互いに素であるかどうか、すなわち最大公約数がいくらであるかを調べる最良のアルゴリズムとしてユークリッドの互除法がある。これによって素因数分解によらずに最大公約数が求まり、互いに素であるかどうかを知ることができる。


ということで「ユークリッド互除法」をヤッホーで調べてみます。
Wkikipedia ユークリッド互除法
http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95

アルゴリズム

1. 入力を m, n (m ≧ n) とする。
2. n = 0 なら、 m を出力してアルゴリズムを終了する。
3. n が m を割り切るなら、 n を出力してアルゴリズムを終了する。
4. m を n で割った余りを新たに m とし、更に m と n を取り替えて 3. に戻る。

上記の手順は「n, m に対して剰余の演算を行うことができる」という仮定だけに依っているので、整数環だけではなく任意のユークリッド整域においても同様にして最大公約因子を求めることができる。

なるほど。。。
とすると、最大公約数はこんな感じで求められるかな?

(define (gcd m n)
  (if (zero? n)
      (abs m)
      (gcd n (remainder m n))))

いまの僕のfiltered-accumulateの実装だと、filterはパラメータを一つしか獲ることができない。
filtered-accumulateはパラメータ「filter」をパラメータ数が1の関数として渡す必要がある。
だから、「公約数を求めるための大きい方のパラメータがあらかじめセット」してあって、
「公約数を求めるための小さい方のパラメータ1つ」で動く関数
を出力する関数を、あらかじめ作っておく必要がある。
(ややこしい!!!)


ちょうど、P34の後半はlambdaなのでちょっと先取りして使ってしまおう。
ち、ちえんひょうか、遅延評価!!(なのか?)


そんで、filtered-accmulateのパラメータに、filterをしこむタイミングで、
関数を実行させてやれば、filterパラメータには、僕が作った関数から作られた、
フィルターとなる関数が与えられる。


そんな気持ちで実装していくと、たぶんこんなのが生まれる。

(define (filter-maker m)
  (lambda (n)
         (if (= 1 (gcd m n)) #t
          #f)))

名前は適当に「filter-maker」笑


ということで、これらを利用して作ってみる。
ソース全体はこんな感じなりました。

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(define (square n)
  (* n n))

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


;;prime? の実装
(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 (cond ((= test-divisor 2) 3 )
                                    (else (+ test-divisor 2)))))))
(define (prime? n)
  (cond ((= n (smallest-divisor n)) #t)
  (else #f)))
;; prime?終わり。

;;再帰的プロセス
(define (filtered-accumulate combiner null-value term a next b filter)
  (if (> a b)
    null-value
    (cond ((filter a)
           (combiner (term a)
                     (filtered-accumulate combiner null-value term (next a) next b filter)))
          (else (filtered-accumulate combiner null-value term (next a) next b filter)))))


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


;;問題bのための準備
(define (gcd m n)
  (if (= 0 n)
    (abs m)
    (gcd n (remainder m n))))


(define (filter-maker m)
  (lambda (n)
    (if (= 1 (gcd m n)) #t
      #f)))

(define (do-nothing a) a)

(define (main args)
  (display "P34 1-33 aの解答 1から10の素数の二乗を全部足したやつ。")(newline)
  (display "再帰的プロセス: (filtered-accumulate + 0 square 1 inc 10 prime?) : ")
  (display (filtered-accumulate + 0 square 1 inc 10 prime?))(newline)
  (display "反復的プロセス: (filtered-accumulate-r + 0 square 1 inc 10 prime?) : ")
  (display (filtered-accumulate-r + 0 square 1 inc 10 prime?))(newline)

  (newline)
  (display "P34 1-33 bの解答 1から10、10とお互いに素で、10より小さい正の整数の積")(newline)
  (display "再帰的プロセス: (filtered-accumulate * 0 do-nothing 1 inc 10 (filter-maker 10)) : ")
  (display (filtered-accumulate * 1 do-nothing 1 inc 10 (filter-maker 10)))(newline)
  (display "反復的プロセス: (filtered-accumulate-r * 0 do-nothing 1 inc 10 (filter-maker 10)) : ")
  (display (filtered-accumulate-r * 1 do-nothing 1 inc 10 (filter-maker 10)))(newline)

 0)


実行してみる。

P34 1-33 aの解答 1から10の素数の乗を全部足したやつ。
再帰的プロセス: (filtered-accumulate + 0 square 1 inc 10 prime?) : 88
反復的プロセス: (filtered-accumulate-r + 0 square 1 inc 10 prime?) : 88

P34 1-33 bの解答 1から10、10とお互いに素で、10より小さい正の整数の積
再帰的プロセス: (filtered-accumulate * 0 do-nothing 1 inc 10 (filter-maker 10)) : 189
反復的プロセス: (filtered-accumulate-r * 0 do-nothing 1 inc 10 (filter-maker 10)) : 189


どうかな?