SICP 問題 2.29（ツリー構造のデータの扱いとか、list と cons の違いとか・・・）

クソ長え・・・

【問題】

二進モービルは、左の枝と右の枝の二つの枝でできている。それぞれの枝はある長さの棒で、そこから錘（おもり）か、別の二進モービルがぶら下がっている。二進モービルを二つの枝から（例えば list を使って）できている合成データで表現できる：

(define (make-mobile left right)
  (list left right))

一つの枝は length （数でなければならない）と、（単なる錘を表現する）数か別のモービルかである　structure で構成する：

(define (make-branch length structure)
  (list length structure))

a. これに対応する選択子（モービルの枝を返す）left-branch と right-branch と、（枝の部品を返す）branch-length と branch-structure を書け。
b. この選択子を使い、モービルの全重量を返す手続き total-weight を定義せよ。
c. モービルは最上段左の枝による回転力、最上段右の枝による回転力が等しく、（つまり左の棒の長さと棒の左にかかっている重さを掛けたものが右側の対応する積に等しく、）しかも枝にぶら下がっている部分モービルのそれぞれが釣り合っているとき、釣り合っている（balanced）という。二進モービルが釣り合っているかどうかをテストする述語を設計せよ。
d. 構成子が、

(define (make-mobile left right)
  (cons left right))

(define (make-branch length structure)
  (cons length structure))

となるようにモービルの表現を変更したとする。新しい表現に対応するにはプログラムをどのくらい変更しなければならないか。

【解答】

「モービル」ってのが「スノーモービル」とシンクロして乗り物ってイメージが。。
ま、いいや。解いていこう。

a

a. これに対応する選択子（モービルの枝を返す）left-branch と right-branch と、（枝の部品を返す）branch-length と branch-structure を書け。

それぞれ定義していくだけ。合成データを生成する際に list を使っており、
更に mobile も branch も要素にリストがあるので２つ目の要素を取得する際に注意が必要。

(define (left-branch mobile)
  (car mobile))

(define (right-branch mobile)
  (car (cdr mobile)))

(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (car (cdr branch)))

さて、では実験。まずは必要なデータを作ってみる。

gosh> (define left-1 (make-branch 2 5))

left-1

gosh> left-1

(2 5)

gosh> (define right-1 (make-branch 3 2))

right-1

gosh> right-1

(3 2)

gosh> (define mobile-1 (make-mobile left-1 right-1))

mobile-1

gosh> mobile-1

((2 5) (3 2) )

gosh> 

続いて定義した手続きを使って動作を確認。

gosh> (left-branch mobile-1)

(2 5)

gosh> (right-branch mobile-1)

(3 2)

gosh> (branch-length left-1)

2

gosh> (branch-length right-1)

3

gosh> (branch-structure left-1)

5

gosh> (branch-structure right-1)

2

gosh> 

いーんじゃないでしょうか。

b

b. この選択子を使い、モービルの全重量を返す手続き total-weight を定義せよ。

モービル、枝、それぞれの重量は０として扱っちゃう。

;枝の重さを計算
(define (branch-weight branch)
  (let ((structure (branch-structure branch)))
    (if (number? structure)
	structure
	(mobile-weight structure))))

;１つのモービルの重さを計算
(define (mobile-weight mobile)
  (let ((left (left-branch mobile))
	(right (right-branch mobile)))
    (+ (branch-weight left)
       (branch-weight right))))

;全重量を計算
(define (total-weight mobile)
  (mobile-weight mobile))

これ、末尾再帰ってできんのか？多分できないと思うんだが。。
それに拘らなければ、ロジック的には別に難しくはないっすね。では、実験。
モービルが入れ子になったテストデータを作成しよう。

gosh> (define left-2 (make-branch 8 mobile-1))

left-2

gosh> (define right-2 (make-branch 4 7))

right-2

gosh> (define mobile-2 (make-mobile left-2 right-2))

mobile-2

gosh> mobile-1

((2 5) (3 2) )

gosh> mobile-2

((8 ((2 5) (3 2))) (4 7))

では総重量を求めてみよう。

gosh> (total-weight mobile-1)

7

gosh> (total-weight mobile-2)

14

gosh> 

おっけ〜っすね。

c

c. モービルは最上段左の枝による回転力、最上段右の枝による回転力が等しく、（つまり左の棒の長さと棒の左にかかっている重さを掛けたものが右側の対応する積に等しく、）しかも枝にぶら下がっている部分モービルのそれぞれが釣り合っているとき、釣り合っている（balanced）という。二進モービルが釣り合っているかどうかをテストする述語を設計せよ。

述語って、要するに balanced? 的な名前の手続きを定義すりゃいいってことだよな？
じゃ、やってみよう。定義はこんな感じか？

;枝の回転力を求める手続きを定義。
(define (moment branch)
  (let ((len (branch-length branch))
	(structure (branch-structure branch)))
    (cond ((number? structure)
	   (* len structure))
	  ((balanced? structure)
	   (* len (mobile-weight structure)))
	  (else
	   #f))))

;釣り合い状況を確認
(define (balanced? mobile)
  ;左の回転力と右の回転力を求め、それらが等しく、かつ
  (let ((left (moment (left-branch mobile)))
	(right (moment (right-branch mobile))))
    (and (eq? left right)
	 (not (eq? left #f)))))

mobile-1 も mobile-2 も釣り合ってない。

gosh> (balanced? mobile-1)

#f

gosh> (balanced? mobile-2)

#f

gosh> 

等しい回転力を保つ mobile-3、mobile-4 を作ってみる。

gosh> (define left-3 (make-branch 3 4))

left-3

gosh> (define right-3 (make-branch 2 6))

right-3

gosh> (define mobile-3 (make-mobile left-3 right-3))

mobile-3

gosh> (define left-4 (make-branch 10 1))

left-4

gosh> (define right-4 (make-branch 1 mobile-3))

right-4

gosh> (define mobile-4 (make-mobile left-4 right-4))

mobile-4

gosh> 

で、mobile-3、mobile-4 をそれぞれチェックしてみよう。両方とも評価結果は #t になるはず。

gosh> (balanced? mobile-4)

#t

gosh> (balanced? mobile-3)

#t

gosh> 

おっけい。

d

d. 構成子が、
(define (make-mobile left right)

  (cons left right))
(define (make-branch length structure)

  (cons length structure))
となるようにモービルの表現を変更したとする。新しい表現に対応するにはプログラムをどのくらい変更しなければならないか。

第2要素を取り出す選択子は変更が必要。

(define (right-branch mobile)
  (cdr mobile))

(define (branch-structure branch)
  (cdr branch))

これだけでいいんじゃないの？いちいちチェックするの面倒くせ〜。。

gosh> (left-branch mobile-1)

(2 . 5)

gosh> (right-branch mobile-1)

(3 . 2)

gosh> (branch-length left-1)

2

gosh> (branch-length right-1)

3

gosh> (branch-structure left-1)

5

gosh> (branch-structure right-1)

2

gosh> (total-weight mobile-1)

7

gosh> (total-weight mobile-2)

14

gosh> (balanced? mobile-1)

#f

gosh> (balanced? mobile-2)

#f

gosh> (balanced? mobile-3)

#t

gosh> (balanced? mobile-4)

#t

gosh> 

以上！あ〜長かった。。