プログラミング再入門

プログラミングをもう一度ちゃんと勉強する読書ノート

SICP 2.2.2 Hierarchical Structures

LISP Scheme

ノート

階層構造。リストの要素としてリストを含む構造。木構造。
データ構造が再帰的な場合それを扱う関数も再帰的に定義するのが自然。

Exercise 2.24
(list 1 (list 2 (list 3 4)))

を図2.6の様な木構造の図にすると。（微妙に節の部分の表現が違うけど）

(1 (2 (3 4)))
  ／   ＼
1      (2 (3 4))
        ／   ＼
       2     (3 4)
            ／   ＼
           3       4
Exercise 2.25
> (car (cdr (car (cdr (cdr '(1 3 (5 7) 9))))))
7
> (car (car '((7))))
7
>

次のは少しややこしい。cdrが残りのリストではなく『リストをひとつ含んだリスト』になっている。

> (cdr '(1 (2 (3 (4 (5 (6 7)))))))
((2 (3 (4 (5 (6 7))))))
> (car (cdr '(1 (2 (3 (4 (5 (6 7))))))))
(2 (3 (4 (5 (6 7)))))
>

なので、cdrの後で追う一度carしないと後続のリストに辿り着かない。

> (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr '(1 (2 (3 (4 (5 (6 7))))))))))))))))))
7
>
Exercise 2.26

実行した結果は以下の通り。

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

考え方は以下の通り：

  1. リストではなく単独の要素の場合、ひっくり返し様がないのでその要素そのもの
  2. リストがひとつの要素しか含まない場合（cdrがnull）
    1. その要素がリストであれば、それをひっくり返したものを要素とするリスト
    2. そのリストそのもの
  3. 複数の要素を持つリストの場合
    1. cdrをひっくり返したリストとcarをひっくり返してそれをリストにしたものリストを連結（append）したリスト

Exercise 2.18の時と同様にcarをひっくり返した後cdrの後ろに付けるにはリストの要素にする必要がある。

(define (deep-reverse l)
  (cond ((not (pair? l)) l)
        ((null? (cdr l)) (if (pair? (car l))
                             (list (deep-reverse (car l)))
                             l))
        (else (append (deep-reverse (cdr l))
                      (list (deep-reverse (car l)))))))

実行してみる。

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

場合分けは３つ：

  1. 引数が空（各リストの最後尾）の場合、空リスト
  2. 引数が要素（ペアでない）の場合、その要素をリストにしたもの
  3. それ以外は、carにfringeを適用したものと、cdrにfringeを適用したものの結合
(define (fringe t)
  (cond ((null? t) t)
        ((not (pair? t)) (list t))
        (else (append (fringe (car t)) (fringe (cdr t))))))

(not (pair? t))がちょっとイケてないが、空→要素→リストと言う順番に考えるとこうなる。よくある答えはnotがなくてelseの部分と逆になっている。

Exercise 2.29

モビールの問題。
a.

(define (left-branch mobile)
  (car mobile))
(define (right-branch mobile)
  (car (cdr mobile)))

right-branchは単にcdrだけだと、make-mobileに渡したrightを含んだリストになってしまうので、更にcarでrightだけを取り出す必要がある。

(define (branch-length branch)
  (car branch))
(define (branch-structure branch)
  (car (cdr branch)))

構造はmobileと全く同じ。

b.

  1. 引数が要素（branchではない）場合は、それが重さ
  2. 引数がリスト（branch）の場合、左の重さと右の重さの合計

正しく作られたmobileが渡される限り、引数に空リストが渡って来る事はない。

(define (total-weight obj)
  (if (not (pair? obj)) obj
      (+ (total-weight (branch-structure (left-branch obj)))
         (total-weight (branch-structure (right-branch obj))))))

実行結果

> (define m (make-mobile (make-branch 10 (make-mobile (make-branch 10 1) (make-branch 10 1))) (make-branch 10 1)))
> m
((10 ((10 1) (10 1))) (10 1))
> (total-weight m)
3
>

c.
モビールは左右の支点に対するモーメント（トルク）が釣り合っている。
実際には下の竿がバランスして*1いなくてもその上の竿はバランスしているケースもある筈だが、この場合はfalseになるべきなので、ある竿がバランスしているとは『その竿の左右のトルクが等しく、かつ左右にぶら下がっているものもそれぞれバランスしている事』と定義する必要がある。錘そのものはバランスしていると考える。
補助関数としてトルクを計算するtorgueと錘かどうかの述語weight?も定義する。

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

実行してみる。

> (define m (make-mobile (make-branch 10 (make-mobile (make-branch 10 1) (make-branch 10 1))) (make-branch 10 1)))
> m
((10 ((10 1) (10 1))) (10 1))
> (balanced? m)
#f
> (define n (make-mobile (make-branch 10 (make-mobile (make-branch 10 1) (make-branch 10 2))) (make-branch 10 3)))
> n
((10 ((10 1) (10 2))) (10 3))
> (balanced? n)
#f
> (define o (make-mobile (make-branch 10 (make-mobile (make-branch 20 1) (make-branch 10 2))) (make-branch 10 3)))
> o
((10 ((20 1) (10 2))) (10 3))
> (balanced? o)
#t
>

mは最初の竿の左が長さ10の所に合計の重さ２、右は長さ10の所に重さ１なのでバランスしていない。
nは最初の竿は左右とも長さ10に重さが３なのでバランスしているが、左にぶら下がっている２番目の竿が、長さが左右とも10だが、重さが左は１に対して右は２なのでバランスしていない。
oはnと殆ど同じだが、左にぶら下がっている２番目の竿が、左が長さ20に重さ１、右が長さ10に重さ２でバランスしているので全体もバランスしている。

d.
各構造体の2番目の値へのセレクタが、(car (cdr ..))ではなく単に(cdr ...)になる。

(define (right-branch mobile)
  (cdr mobile))

(define (branch-structure branch)
  (cdr branch))

変更はこれだけで、total-weightもbalanced?もそのままでちゃんと動作する。

Mapping over trees

木構造データに対するmap。
scale-treeを動かしてみる。（nilはnullに変更。DrRacketの#schemeモード）

> (define (scale-tree tree factor)
    (cond ((null? tree) null)
          ((not (pair? tree)) (* tree factor))
          (else (cons (scale-tree (car tree) factor)
                      (scale-tree (cdr tree) factor)))))
> (scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))
              10)
(10 (20 (30 40) 50) (60 70))
>

treeって引数で受け取っても、treeじゃなくleaveのケースがあるので引数の名前は難しい。
mapを使ったscale-treeも動かしてみる。

> (define (scale-tree tree factor)
    (map (lambda (sub-tree)
           (if (pair? sub-tree)
               (scale-tree sub-tree factor)
               (* sub-tree factor)))
         tree))
> (scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))
              10)
(10 (20 (30 40) 50) (60 70))
>
Exercise 2.30

構造はscale-treeと全く同じ。

(define (square-tree1 tree)
  (cond ((null? tree) null)
        ((not (pair? tree)) (* tree tree))
        (else (cons (square-tree1 (car tree))
                    (square-tree1 (cdr tree))))))

実行結果。

> (square-tree1
   (list 1
         (list 2 (list 3 4) 5)
         (list 6 7)))
(1 (4 (9 16) 25) (36 49))
>

mapを使った実装。

(define (square-tree2 tree)
  (map (lambda (tree)
         (if (pair? tree) (square-tree2 tree)
             (* tree tree)))
       tree))

実行結果

> (square-tree2
   (list 1
         (list 2 (list 3 4) 5)
         (list 6 7)))
(1 (4 (9 16) 25) (36 49))
>
Exercise 2.31

構造が全く同じ二つの関数が出来たら当然共通部分を括り出す。

(define (tree-map proc tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree) (tree-map proc sub-tree)
             (proc sub-tree)))
       tree))

(define (square x) (* x x))
(define (square-tree tree) (tree-map square tree))

(define (scale-tree tree factor)
  (tree-map (lambda (leave) (* leave factor)) tree))

こうすると無名関数の引数にはleaveしか渡されないので名前もスッキリ。
実行結果。

> (scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))
              10)
(10 (20 (30 40) 50) (60 70))
> (square-tree
   (list 1
         (list 2 (list 3 4) 5)
         (list 6 7)))
(1 (4 (9 16) 25) (36 49))
>
Exercise 2.32

リストで集合（要素の重複がない）を表現。その集合の全ての部分集合を列挙。

(define (subsets s)
  (if (null? s)
      (list null)
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (a)
                            (cons (car s) a))
                          rest)))))

実行結果。

> (subsets (list 1 2 3))
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
>

両替の問題の考え方と少し似ている。
集合の最初の要素（X）を取り上げて、その集合の全ての部分集合はXを含んでいないグループ（A）と含んでいるグループ（B）に分類出来る。AはXを含まない集合の全ての部分集合なので縮小した問題となって同様の考え方で列挙可能。BはAの全ての要素（部分集合）にそれぞれXを追加したもの。
リストで考えると：

  1. (A)cdrにsubsetsを適用した結果
  2. (B)Aの結果のそれぞれにcarを追加した集合

の和と定義出来る。挙動を追うと、与えられた集合（リスト）の最後尾まで行ってから、帰り道で以下の様に部分集合を作って行く。

car 結果
なし ()
3 () + (3)
2 () (3) + (2) (2 3)
1 () (3) (2) (2 3) + (1) (1 3) (1 2) (1 2 3)

*1:『バランスする』と言う言葉遣いは変なのかも知れないが、『バランスが取れている』と言ってもこちらが正しいとも言い切れないので字数が少ない方を採用する。英語のbalancedが過去分詞で受動態と捉えると『バランスされている』となるがこの言い回しは聞いた事がない。