Edited at

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

hiroshi-manabe様の日本語訳を使わせてもらいます。

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

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

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

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

モビールの総重量を返す手続き`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
```

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