SICP読書録 #23 2.2.2 階層構造 - 練習問題 2.29

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

前回はこちら

2.2.2 階層構造

リストの要素をリストにできる。つまり階層構造を取れる。

_.scm

gosh> (cons (list 1 2) (list 3 4))
((1 2) 3 4)

階層構造は木構造と見なせる。図にするとこう。

((1 2) 3 4) --- (1 2) --- 1
             |         |- 2
             |- 3
             |- 4

ここで、この木構造の葉の数を数える手続きを作る。

_.scm

(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

実行してみよう。

_.scm

gosh> (define x (cons (list 1 2) (list 3 4)))
gosh> (count-leaves x)
4

練習問題 2.24

(list 1 (list 2 (list 3 4))) を図示する。

(1 (2 (3 4)) --- 1
              |- (2 (3 4)) --- 2
                            |- (3 4) --- 3
                                      |- 4

練習問題 2.25

carとcdrを使って、与えられたリストから 7 を取り出す。

_.scm

gosh> (define x `(1 3 (5 7) 9))
gosh> (cdr x)
(3 (5 7) 9)
gosh> (cdr (cdr x))
((5 7) 9)
gosh> (car (cdr (cdr x)))
(5 7)
gosh> (cdr (car (cdr (cdr x))))
(7)
gosh> (car (cdr (car (cdr (cdr x)))))
7

_.scm

gosh> (define x `((7)))
gosh> (car x)
(7)
gosh> (car (car x))
7

_.scm

gosh> (define x `(1 (2 (3 (4 (5 (6 7)))))))
gosh> (cdr x)
((2 (3 (4 (5 (6 7))))))
gosh> (car (cdr x))
(2 (3 (4 (5 (6 7)))))
gosh> (cdr (car (cdr x)))
((3 (4 (5 (6 7)))))
gosh> (car (cdr (car (cdr x))))
(3 (4 (5 (6 7))))
gosh> (cdr (car (cdr (car (cdr x)))))
((4 (5 (6 7))))
gosh> (car (cdr (car (cdr (car (cdr x))))))
(4 (5 (6 7)))
gosh> (cdr (car (cdr (car (cdr (car (cdr x)))))))
((5 (6 7)))
gosh> (car (cdr (car (cdr (car (cdr (car (cdr x))))))))
(5 (6 7))
gosh> (cdr (car (cdr (car (cdr (car (cdr (car (cdr x)))))))))
((6 7))
gosh> (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr x))))))))))
(6 7)
gosh> (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr x)))))))))))
(7)
gosh> (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr x))))))))))))
7

練習問題 2.26

書いてある通りに動かすだけの問題。

_.scm

gosh> (define x (list 1 2 3))
gosh> (define y (list 4 5 6))
gosh> (append x y)
(1 2 3 4 5 6)
gosh> (cons x y)
((1 2 3) 4 5 6)
gosh> (list x y)
((1 2 3) (4 5 6))

練習問題 2.27

リストを再帰的に逆順にする手続きdeep-reverseを作る。

_.scm

(define (deep-reverse items)
  (if (pair? items)
    (append (deep-reverse (cdr items))
            (list (deep-reverse (car items))))
    items))

実行結果。

_.scm

gosh> (define x (list (list 1 2) (list 3 4)))
gosh> (deep-reverse x)
((4 3) (2 1))

練習問題 2.28

木構造をフラットにする手続きfringe。

_.scm

(define (fringe items)
  (cond
    ((null? items) ()) 
    ((not (pair? items)) (list items))
    (else (append (fringe (car items))
                  (fringe (cdr items))))))

実行結果。

_.scm

gosh> (define x (list (list 1 2) (list 3 4)))
gosh> (fringe x)
(1 2 3 4)
gosh> (fringe (list x x))
(1 2 3 4 1 2 3 4)

練習問題 2.29

左右２つの「枝」からなる「二枝モビール(mobile)」というデータ構造を表現してみよう。
ここで「枝」とは長さと構造から成り立ち、長さは数値、構造は数値（重量を表す）かモビールである。

_.scm

(define (make-mobile left right)
  (list left right))
(define (make-branch length structure)
  (list length structure))

モビールの枝を返すセレクタ left-branch、right-branch、枝の構成要素を返すbranch-length、branch-structureを定義する。

_.scm

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

モビールを適当に2つほど作っておこう。

_.scm

(define x (make-mobile
  (make-branch 4 (make-mobile (make-branch 1 2) (make-branch 2 1)))
  (make-branch 6 2)))

(define y (make-mobile
  (make-branch 3 6)
  (make-branch 4 (make-mobile (make-branch 3 4) (make-branch 4 3)))))

枝の総重量を返す手続きbranch-weightと、
モビールの総重量を返す手続きtotal-weightを定義する。

_.scm

(define (branch-weight branch)
  (let ((structure (branch-structure branch)))
    (if (pair? structure) (total-weight structure) structure)))

(define (total-weight mobile)
  (+ (branch-weight (left-branch mobile))
     (branch-weight (right-branch mobile))))

動かしてみる。

_.scm

gosh> (total-weight x)
5
gosh> (total-weight y)
13

枝の長さと重量を掛けると、トルク（回転力）が得られる。全ての左右枝のトルクがそれぞれ等しければ、バランスが取れていると言える。バランスが取れているかを返す手続きbalanced?を作ってみよう。

_.scm

(define (balanced? mobile)
  (define (torque branch)
    (* (branch-length branch) (branch-weight branch)))
  (define (branch-balanced? branch)
    (let ((structure (branch-structure branch)))
      (if (pair? structure) (balanced? structure) #t)))
  (let ((left  (left-branch  mobile))
        (right (right-branch mobile)))
    (and (= (torque left) (torque right))
      (branch-balanced? left)
      (branch-balanced? right))))

実行結果。

_.scm

gosh> (balanced? x)
# t
gosh> (balanced? y)
# f

モビールの表現を次のように変えても、total-weightやbalanced?は動作する。

_.scm

(define (make-mobile left right) (cons left right))
(define (make-branch length structure) (cons length structure))
(define (left-branch mobile) (car mobile))
(define (right-branch mobile) (cdr mobile))
(define (branch-length branch) (car branch))
(define (branch-structure branch) (cdr branch))