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