問題1-32〜33

今日は、｢高階手続きによる抽象｣をより体感するために、問題1-32〜33に取り組みました。第一章の第三節は、バラバラだった手続きがどんどんまとめられていく過程を楽しめて非常に面白いのですが、この問題では、本文では気づかなかった抽象化の過程を実感することができました。
まずは、問題1-32です。sumやproductに抽象化された手続きを、さらに抽象化するための問題です。似たようなことを書いていたら、それは抽象化できるサインだということを痛感しましたが、combinerの定義をするところは、いまいち上手くまとめられませんでした。lambdaとかを使えば上手くいきそうな予感ですが、この問題の段階では習っていない技なので、それは使っていません。このあたりについては、あとで調査してみたいと思っています。以下は、再帰的なプロセスで実行されるコードです。

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

(define (product term a next b)
  (define (combiner x y)
    (* x y))
  (accumulate combiner 1 term a next b))

(define (sum term a next b)
  (define (combiner x y)
    (+ x y))
  (accumulate combiner 0 term a next b))

反復的なプロセスだと、以下のようになると考えられます。

(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))

次の問題1-33ですが、filter用のsum/product手続きを定義する方法しか思いつかず、これが微妙な感じがしましたが、とりあえずは動くコードを書くことができました。以下は、accumulate手続きを改良したバージョンです。

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

filter手続きには、操作対象となっている変数と終着点である変数の二つを渡しています。問題aの方では前者だけで足りるのですが、問題bの方では両方必要になってくるので、このようにしました。このfiltered-accumulateを呼び出すために、sum/productの改良バージョンを作ってしまいましたが、これで正しいのかは皆目疑問です。(もとのsum/productというインターフェイスの引数を変えずにfilter機能を実装する手段があるのかもしれません)

(define (filtered-sum filter term a next b)
  (define (combiner x y)
    (+ x y))
  (filtered-accumulate combiner 0 filter term a next b))

(define (filtered-product filter term a next b)
  (define (combiner x y)
    (* x y))
  (filtered-accumulate combiner 1 filter term a next b))

問題aでは、上記filtered-sumを以下のように呼び出してみました。prime-filterでは二つの引数を渡していますが、後者は必要ないため無視しています。こういう書き方がよろしいのかどうかは、あとで調べてみたいトピックです。(以前書いた自分のprime?実装では、1が素数と判定されてしまうため正しい答えが返ってきませんでした)

(define (prime-filter tgt to)
  (prime? tgt))

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

(define (inc n) (+ n 1))

(define (prime-square-sum from to)
  (filtered-sum prime-filter square from inc to))
  
(prime-square-sum 10 30)

=>2310

問題bは、以下のようなコードを書いたら、正しいであろう答えが返ってきました。調査対象となる任意の整数をトリガーとして、gcdを使い1から調べていくというロジックです。

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

(define (gcd-filter tgt to)
  (= (gcd tgt to) 1))

(define (identity x) x)

(define (inc n) (+ n 1))

(define (gcd-product to)
  (filtered-product gcd-filter identity 1 inc to))

(gcd-product 10)

=>189

まだ自分で書いたコードと他の人が書いたコードを比較してみるという作業には取りかかれていませんが、これはやらなければもったいないことなので、勉強会やウェブ世界に溢れている情報を上手いこと活用していき、そんなこともこのブログに書いていけたら良いなと思っています。