Edited at

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

carcdrを使って、与えられたリストから 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

左右2つの「枝」からなる「二枝モビール(mobile)」というデータ構造を表現してみよう。

ここで「枝」とは長さと構造から成り立ち、長さは数値、構造は数値(重量を表す)かモビールである。


_.scm

(define (make-mobile left right)

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

モビールの枝を返すセレクタ left-branchright-branch、枝の構成要素を返すbranch-lengthbranch-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-weightbalanced?は動作する。


_.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))