SICP読書録 #17 2 データを用いた抽象化の構築 - 練習問題2.1

hiroshi-manabe様の日本語訳を使わせてもらいます。
練習問題等はGaucheで実行。

前回はこちら

2 データを用いた抽象化の構築

これまでは、手続きについてあれこれと学んできた。基本手続きを組み合わせることによって作成される複合手続きにより、プログラム設計における概念レベルを引き上げることができた。

同様に、ここからは複合データを学んでいこう。複合データによって基本データよりも高い概念レベルでデータを扱えるようになる。

「データを内部的にどう表現するか」と「データをどのように扱うか」を分離することをデータ抽象化という。
これにより、「データを扱う人」は、「そのデータがどう表現されているか」などという細かいことに煩わされる必要がなくなる。プログラムの部品間に適切な抽象化の壁を建てられるようになり、複雑さを抑えることが可能になるのだ。

複合データを部品として扱えるようにするためには、それが標準インターフェースとして利用できなければならない。

2.1 データ抽象化入門

2.1.1 例：有理数の数値演算

有理数に対する演算を行うことを考えよう。Schemeの基本データ型には「有理数」などというものはない。が、次のような手続きがすでにあると仮定すれば、

• (make-rat n d) 分子がnで、分母がdの有理数を返す。
• (numer x) 有理数xの分子を返す
• (denon x) 有理数xの分母を返す

有理数に対する加減乗除と等価性判定の手続きは書ける。たとえ、その「有理数」の具体的な表現方法について知らなくてもだ。

_.scm

(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))

(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))

(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

ペア

じゃあそろそろ「有理数」の具体的な表現方法について考えるとしよう。Schemeにはcons,car,cdrという手続きがあり、これを使うとペアという複合データオブジェクトを扱える。

_.scm

gosh> (define x (cons 1 2))
x
gosh> (car x)
1
gosh> (cdr x)
2

ペアの要素をペアにすることだってできる。

_.scm

gosh> (define y (cons 3 4))
y
gosh> (define x (cons 1 2))
x
gosh> (define y (cons 3 4))
y
gosh> (define z (cons x y))
z
gosh> (car (car z))
1
gosh> (car (cdr z))
3

有理数を表現する

有理数はペアを使って表現すればよいだろう。make-rat,numer,denimは次のように実装できる。

_.scm

(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))
;有理数を表示する手続きも作っておく
(define (print-rat x)
  (print (numer x) "/" (denom x)))

これで、さっき実装した演算はすべて何の変更も加えることなく実行できる。

_.scm

gosh> (define one-half (make-rat 1 2))
one-half
gosh> (print-rat one-half)
1/2
gosh> (define one-third (make-rat 1 3))
one-third
gosh> (print-rat (add-rat one-half one-third))
5/6
gosh> (print-rat (mul-rat one-half one-third))
1/6
gosh> (print-rat (add-rat one-third one-third))
6/9

最後の例は、返してきた答えがダサい。2/3って返して欲しい。make-ratを改善しよう。
以前に作った最大公約数を求める手続きgdcを使う。

_.scm

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))

実行結果。

_.scm

gosh> (print-rat (add-rat one-third one-third))
2/3

練習問題 2.1

分子と分母にそれぞれ正負の数が混じってたらどうなる？
先に、既約とするためにgdcで割るという操作を追加したため、符号が反転する場合がある。

_.scm

gosh> (print-rat (make-rat 1 -3))
1/-3
gosh> (print-rat (make-rat -1 3))
1/-3
gosh> (print-rat (make-rat -1 -3))
1/3

分子と分母の符号が異なっていたら、分子のみマイナスとなるようにしよう。

_.scm

(define (make-rat n d)
  (let ((g (gcd n d)))
    (let ((n (/ n g))
          (d (/ d g)))
      (if (and (>= n 0) (< d 0))
        (cons (* -1 n) (* -1 d))
        (cons n d)))))

実行結果。

_.scm

gosh> (print-rat (make-rat 1 -3))
-1/3
gosh> (print-rat (make-rat -1 3))
-1/3
gosh> (print-rat (make-rat -1 -3))
1/3