＊「ふっかつのじゅもんがちがいます。」

Buzzurlの中の人日記

DQ4

弊社のインフラチームのネ申いわゆるゴッドであるところのY村さんが

「DQ4 DSが何時間遊べようが関係ない暇つぶし方法を思いついた
ロードランナーだ！！！
Wryyyyyyyy!!!!!!!!!」

的なことをタバコ部屋で言っていた。

2008/02/04 (Mon) 毎日がエブリデイ Trackback(0) Comment(0)

▲top

SICP練習問題1.1～1.3

SICPの読書会ちゃんとやってます。週一回。

2回やって練習問題1.3まで来ました。淡々と答案を書こうと思います。schemeは全然分かってないので、識者の方は突っ込みお願いします。

1.1 式を評価した結果を答えよ省略

1.2 式を前置記法で書け省略

1.3 3つの数を引数に取りその中の大きいもの二つの平方の和を返す手続きを定義せよ。

ここまでに出てきているschemeの要素は以下。

変数/関数定義
条件分岐
論理和/論理積

以上の要素だけを使って馬鹿正直に書くとこう。

でもこんな if/else だらけのコードを書くためにSICP読んでるわけじゃないのであとでもうちょっと何とかしてみる。

(define (square x) (* x x))
(define (ex1-3-1 x y z)
  (cond ((and (< x y) (< x z)) (+ (square y) (square z)))
        ((and (< y x) (< y z)) (+ (square z) (square x)))
        (else (+ (square x) (square y)))))

単体テストはdefine-syntax でユニットテストの素敵なマクロを使ってみる。

このあと別なバージョンの実装もテストするので、テストケースに関数を渡せるように改変。

(define (report-result result form)
  (format #t "[~A] ... ~A~%" (if result "pass" "FAIL") form))
(define-syntax check
  (syntax-rules ()
                ((_ form ...) (begin (report-result form 'form) ...))))

(define (testcase1-3 ex1-3)
  (check
    (= (ex1-3 1 2 3) 13)
    (= (ex1-3 3 1 2) 13)
    (= (ex1-3 3 2 1) 13)
    (= (ex1-3 1 2 2) 8)
    (= (ex1-3 2 1 2) 8)
    (= (ex1-3 2 2 1) 8)
    (= (ex1-3 1 1 1) 2)))

(testcase1-3 ex1-3-1)

[pass] ... (= (ex1-3 1 2 3) 13)
[pass] ... (= (ex1-3 3 1 2) 13)
[pass] ... (= (ex1-3 3 2 1) 13)
[pass] ... (= (ex1-3 1 2 2) 8)
[pass] ... (= (ex1-3 2 1 2) 8)
[pass] ... (= (ex1-3 2 2 1) 8)
[pass] ... (= (ex1-3 1 1 1) 2)

考え方その2

全部足してから一番小さいのだけ引く

2つの数のうち小さい方を返すmin-pair関数を定義してやる。3つの引数をとって最小を返すほうmin-trioとかのほうが綺麗に書けるけどどうみても汎用性がなさすぎる。任意個の引数から最小を返すmy-min関数を実装してもいいけど、ここまでの範囲では書けない。

ただこのやり方は富豪的過ぎるかもしれない。3数ごときならどうでもいいけど。

(define (ex1-3-2 x y z)
  (define (min-pair a b) (if (< a b) a b))
  (+ (square x) (square y) (square z) (- (square (min-pair x (min-pair y z))))))
(testcase1-3 ex1-3-2)

(以下テスト結果は略)

さすがにmin関数くらいは組み込みを使ってもいいかもしれない。ここまでに出てきた要素から逸脱するけれど。

(define (ex1-3-3 x y z)
  (+ (square x) (square y) (square z) (- (square (min x y z)))))
(testcase1-3 ex1-3-3)

考え方その3

何度もsquareを書きたくない。関数型言語なんだからmapくらいあるだろ。minの時点でここまでの範囲を逸脱しちゃったのでここからはもう気にしない。

perlでいうList::Util::reduce、Rubyでいうinjectみたいのは何だろうとしらべたらfoldらしいのでそれを使う。foldには初期値を設定できるので、初期値に (- (square (min x y z))) を渡したら割とすっきり。

(define (ex1-3-4 x y z)
  (fold + (- (square (min x y z))) (map square (list x y z))))
(testcase1-3 ex1-3-4)

考え方その4

考え方その3はあまりにもこの問題の前提条件に依存しすぎている。4引数で上位2つという問題に拡張されたらどうするのか？もうすでに無駄な拡張性確保の領域。設計上やってはいけないことの一つですね。

解き方として、引数をソートしてから上位n個を取り出して2乗して足すという問題の特殊な場合と見る。

sliceとかheadとかそういう関数はなさそうだったのでまずはリストの先頭n個を取り出す関数headを作る（こういう目的の関数ありそうだけど）。

(define (head num ls)
  (define (<= a b) (not (> a b)))
  (if (<= num 0) '() (cons (car ls) (head (- num 1) (cdr ls)))))
(head 3 '(1 2 3 4 5 6))

なんか非効率な実装のような気もする。

次に2乗の和を求める関数sum-of-square（必要ない気もするけど式が長くなっていやだったので切り分けた）

(define (sum-of-square ls)
  (fold + 0 (map square ls)))

最後にリストの上位n個リストを返す関数bigger（同上）。

(define (bigger num ls)
  (head num (reverse (sort ls))))

以上を使えばこうなる。当初の問題から逸脱しすぎている。

(define (ex1-3-5 x y z)
  (sum-of-square (bigger 2 (list x y z))))

補助関数の定義はex1-3-5の内部にしちゃって実際にはこう。

(define (ex1-3-5 x y z)
  (define (head num ls)
    (define (<= a b) (not (> a b)))
    (if (<= num 0) '() (cons (car ls) (head (- num 1) (cdr ls)))))
  (define (sum-of-square ls)
    (fold + 0 (map square ls)))
  (define (bigger num ls)
    (head num (reverse (sort ls))))
  (sum-of-square (bigger 2 (list x y z))))