SICPを読む(33) 2.1.1 いよいよリストです。

Scheme

ようやく辿り着きました。今日から2章に突入です。

Schemeと聞いて思いつくのは再帰、ラムダ、リスト・・・ってこれだけしか思いつかないんですが、シンプルなデータ構造にどんな魔術が潜んでいるのか。めちゃくちゃ楽しみです!!

しかし、リストだけで80ページ近くある。何ヶ月かかるのかなぁ・・・(遠い目

まずはcons

(define x (cons 1 2))

x       ; (1 . 2)
(car x) ; 1
(cdr x) ; 2

consで対を作る。「対」ってのがあんまり理解出来てないが、右と左にあると考えればいいのかな・・・。

で、carで左,cdrで右を取り出すと。

次は、有理数。

有理数ってなんだっけ。

って、有理数って何だっけ。

ふむふむ。

整数は有理数。
分数は有理数。
自然対数、円周率、ルートは無理数。

1/3は0.33333333と循環するから有理数。
11/5は2.2で有限少数。
π = 3.1415...はいつまで経っても循環しないから無理数。

要するに分数って事だね。

有理数を定義しよう。

さて、定義していこう。

(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))

(define (rat-to-string x)
  (format "~a/~a" (numer x) (denom x)))
(define (print-rat x)
  (display (rat-to-string x))
  (newline))

(define one-half (make-rat 1 2))
(print-rat one-half)
  • make-ratでリストを作る。コンストラクタみたいな感じだね。
  • numer,denomがgetかな。
  • ってことで、to-stringも定義してみた。改行以外にも表示方法があった方が便利かなぁなんて。

次!データを操作しよう。

(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))
     (* (denom x) (numer y))))

(print-rat (add-rat one-half one-half)) ; 4/4
(print-rat (sub-rat one-half one-half)) ; 0/4
(print-rat (mul-rat one-half one-half)) ; 1/4
(print-rat (div-rat one-half one-half)) ; 2/2
(equal-rat? one-half one-half) ; #t

えっと、えっと、分母と、分子を・・・←小学生以下

頭が悪いのは、プログラムも一緒。1/2 + 1/2 = 4/4って!!

なので、gcdで補正。

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

(print-rat (add-rat one-half one-half)) ; 1/1

おぉ、gcd偉い!!

まとめ

データは抽象化して使おう。