[ 目次, 前節, 次節, 索引 ]

2.2.2 階層構造



リストを使っての並びの表現は, その要素がまた並びであるような並びの表現へと自然に一般化出来る. 例えば
(cons (list 1 2) (list 3 4))
で作ったオブジェクト((1 2) 3 4)は, その最初がそれ自身リスト(1 2)である三つの項のリストと見ることが出来る. 実際これは解釈系が印字した形からも分る. 図2.5は, この構造の対を使った表現を示す.



図2.5 (cons (list 1 2) (list 3 4))で作った構造

   その要素自身が並びであるような並びのもう一つの見方が(tree)である. 並びの要素は木の枝であり, それ自身並びである要素は部分木である. 図2.6は木として見た図2.5の構造を示す.



図2.6 木として見た図2.5のリスト構造

   木に対する演算を, その枝に対する演算へ引き下げ, 更に枝の枝の演算へ引き下げ, 木の葉に至るまで繰り返すことが多いので, 再帰は木構造を扱う自然な道具である. 例えば2.2.1節のlengthの手続きを, 木にある葉の全数を返す count-leaves手続きと比べてみよう.

(define x (cons (list 1 2) (list 3 4)))

(length x)
3

(count-leaves x)
4

(list x x)
(((1 2) 3 4) ((1 2) 3 4))

(length (list x x))
2

(count-leaves (list x x))
8

   count-leavesを実装するには, lengthを計算する再帰的計画を思い出してみよう:

• リストxlengthxcdr length足す1である.

• 空リストのlengthは0である.

count-leavesも同様である. 空リストに対する値も同じ:

• 空リストのcount-leavesは0.

しかし, 引き下げステップでリストのcarを取り出す時, carはその葉を数えるべき木かも知れないことに注意がいる. そこで適切な引き下げのステップは

• 木xcount-leavesxcar count-leaves足すxcdrcount-leavesである.

最後にcarをとりながら葉に至るので, もう一つ基本の場合がある:

• 葉のcount-leavesは1である.

木の再帰的手続きを書くのに役立つよう, Schemeには引数が対であるかどうかテストする基本的述語 pair?が用意してある. これが完成した手続きである:13


(define (count-leaves x)
  (cond ((null? x) 0)  
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

問題 2.24


(list 1 (list 2 (list 3 4)))を評価したとしよう. 解釈系の印字する結果, 対応する箱とポインタ構造および(図2.6のような)木としての解釈を書け.

問題 2.25


次のそれぞれのリストから, 7を取り出すcarcdrの組合せを書け:
(1 3 (5 7) 9)

((7))

(1 (2 (3 (4 (5 (6 7))))))


問題 2.26


xyをリストとして定義したとしよう:
(define x (list 1 2 3))

(define y (list 4 5 6))
次の式のそれぞれの評価に応じて, 解釈系が印字する結果は何か:
(append x y)

(cons x y)

(list x y)


問題 2.27


問題2.18の手続きreverseを修正し, 引数としてリストをとり, 要素を逆順にし, 更に部分木も奥まで逆順にする手続き deep-reverseを作れ. 例えば
(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))


問題 2.28


引数として(リストとして表現されている)木をとり, その要素が, 木のすべての葉を, 左から右の順に並べたものであるリストを返す手続き fringeを書け. 例えば
(define x (list (list 1 2) (list 3 4)))

(fringe x)
(1 2 3 4)

(fringe (list x x))
(1 2 3 4 1 2 3 4)


問題 2.29


二進モービルは, 左の枝と右の枝の二つの枝で出来ている. それぞれの枝はある長さの棒で, そこから錘か, 別の二進モービルがぶら下っている. 二進モービルを二つの枝から(例えばlistを使って)出来ている合成データで表現出来る:
(define (make-mobile left right)
  (list left right))
一つの枝はlength(数でなければならない)と, (単なる錘を表現する)数か別のモービルかであるstructureで構成する:
(define (make-branch length structure)
  (list length structure))
a. これに対応する選択子(モービルの枝を返す)left-branch right-branchと, (枝の部品を返す)branch-length branch-structureを書け.

b. この選択子を使い, モービルの全重量を返す手続きtotal-weightを定義せよ.

c. モービルは最上段左の枝による回転力と, 最上段右の枝による回転力が等しく, (つまり左の棒の長さと棒の左にかかっている重さを掛けたものが右側の対応する積に等しく,) しかも枝にぶら下っている部分モービルのそれぞれが釣合っている時, 釣合っている(balanced)という. 二進モービルが釣合っているかどうかをテストする述語を設計せよ.

d. 構成子が
(define (make-mobile left right)
  (cons left right))

(define (make-branch length structure)
  (cons length structure))
となるようにモービルの表現を変更したとする. 新しい表現に対応するにはプログラムをどのくらい変更しなければならないか.
木の写像
mapが並びを扱う強力な抽象であるのと同様に, 再帰と一緒になったmapは木を扱う強力な抽象である. 例えば2.2.1節のscale-listと類似のscale-tree手続きは, 引数として数値の係数と, 葉が数であるような木をとる. そして同じ形だが, 数のそれぞれが係数倍されている木を返す. scale-treeの再帰的計画はcount-leavesのそれに似ている:

(define (scale-tree tree factor)
  (cond ((null? tree) nil)
        ((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))

   scale-treeを実装するもう一つの方法は, 木を部分木の並びと見, mapを使うことだ. われわれは並びを写像し, 部分木のそれぞれを順に係数倍し,結果のリストを返す. 基底の場合, 木は葉になっているが, 単に係数を掛ける:


(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))
木の演算の多くは, 同様な並びの演算と再帰の組合せで実装出来る.

問題 2.30


問題2.21のsquare-list手続きと類似の手続きsquare-treeを定義せよ. つまりsquare-treeは, 次のように振舞わなければならない.
(square-tree
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))
(1 (4 (9 16) 25) (36 49))
square-treeを直接に(つまり高階手続きを使わずに), またmapと再帰を使って定義せよ.

問題 2.31


問題2.30の答を抽象化し, square-tree
(define (square-tree tree) (tree-map square tree))
と定義出来るように, 手続き tree-mapを作れ.

問題 2.32


集合は相異る要素のリストで表現出来る. また, 集合のすべての部分集合の集合を, リストのリストで表現出来る. 例えば集合が(1 2 3)の時, すべての部分集合の集合は(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))である. 集合の部分集合の集合を作り出す手続きの次の定義を完成し, なぜうまくいくか, 明快に説明せよ.
(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map ⟨??⟩ rest)))))




13 condの初めの二つの節の順には, 意味がある. 空リストはnull?を満足すると同時に対でもない.

[ 目次, 前節, 次節, 索引 ]