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

[hiroshi-manabe様の日本語訳](https://github.com/hiroshi-manabe/sicp-pdf)を使わせてもらいます。
練習問題等は[Gauche](http://practical-scheme.net/gauche/index-j.html)で実行。

[前回はこちら](https://qiita.com/shuetsu@github/items/db00409b96a91bcbca32)

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