8.3 変更可能なデータ構造
問 8.6
dataDlist， rightDlist， leftDlistを定義せよ．
解答例
fun dataDlist (ref (CELL{data,...})) = data
fun rightDlist (ref (CELL{right,...})) = right
fun leftDlist (ref (CELL{left,...})) = left
問 8.7
deleteDlist と fromListToDlist を定義せよ．
解答例
fun deleteDlist dlist =
case dlist of
ref NIL => ()
| ref (CELL{left=l1 as ref (CELL{right=r2,left=l2,...}),
right=r1 as ref (CELL{right=r3,left=l3,...}),
...}) =>
if l1 = l2 then dlist := NIL
else (dlist := !r1; r2 := !r1; l3 := !l1)
fun fromListToDlist L = foldl (fn (x,y) => (insertDlist x y;y)) (ref NIL) (rev L)
補足: fromListToDlistは、リストの末尾から循環リストに追加してい く関数である。 foldrは末尾再帰の実装が困難なため、
fun fromListToDlist L = foldr (fn (x,y) => (insertDlist x y;y)) (ref NIL) Lよりスタックオーバフローなどの危険も少なく効率がよい。
この観点から、リストを生成する関数、例えばtoListなども以 下のような実装が望ましい。fun toList L = let fun loop (l,A) visited = if member l visited then rev A else loop (rightDlist l, dataDlist l::A) (l::visited) in loop (rightDlist (leftDlist L), nil) nil endさらに、循環リストは、リストの末尾からも辿ることができるので、 以下のより効率よい自然なコードが可能である。
fun toList L = let fun loop (l,A) visited = if member l visited then A else loop (leftDlist l, dataDlist l::A) (l::visited) in loop (leftDlist L, nil) nil endまた、循環リストのリスト表現を逆順のリストとする定義すると、 以下の関数となる。
fun toListL L = let fun loop (l,A) visited = if member l visited then A else loop (rightDlist l, dataDlist l::A) (l::visited) in loop (rightDlist (leftDlist L), nil) nil end対応する循環リストへの変換は、
fun fromListToDlistL L = foldl (fn (x,y) => (insert x y;y)) (ref NIL) L
問 8.8
2つの循環2重リストを連結する関数
concatDlist : ’a dlist -> ’a dlsit -> unit
を定義せよ．ただし，連結の結果は，どちらのリストから見ても，セルを右にたど ると，以前のセルの後に他の循環2重リストのセルが付け加えられているようにせ よ．
解答例 以下にコード例を示す。
fun concatDlist D1 D2 =
case (D1, D2) of
(ref NIL, _) => D1 := !D2
| (_, ref NIL) => D2 := !D1
| (ref (CELL{left=d1l as ref (CELL{right=d1lr,...}),...}),
ref (CELL{left=d2l as ref (CELL{right=d2lr,...}),...})) =>
let
val d1lCell = !d1l
val d1lrCell = !d1lr
in
(d1l := !d2l;
d1lr := !d2lr;
d2l := d1lCell;
d2lr := d1lrCell)
end
問 8.9
以下の関数を定義せよ．
-
1.
循環2重リンクリストをコピーする関数 copyDlist．
-
2.
与えられた関数を循環2重リンクリストの各要素に適用して得られる値を要素 とする，新しい循環2重リンクリストを生成する関数 mapDlist．
-
3.
リストの foldr および foldl に相当する関数 foldrDlist および foldlDlist．
解答例 これら関数の適切な定義には、以下の点を含む種々の注意深い考察が必要である。
-
•
循環構造を辿る際の終了条件の適切な判定
-
•
leftおよびrightフィールドをたどると自分自身に戻ってくる CELLへの参照型データの作成
以下に、これら２点を考慮したコード例を示す。なお、copyDlistは mapDlistとほぼ同様なコードであり、後者を使って定義している。
fun mapDlist f d =
let
fun newElem x nil = NONE
| newElem x ((h,newH)::t) =
if x = h then SOME newH
else newElem x t
fun copy l copied =
case l of
ref NIL => ref NIL
| ref (CELL{left, right, data}) =>
(case newElem l copied of
NONE =>
let
val newL = ref NIL
val copied = (l, newL)::copied
val l = copy left copied
val r = copy right copied
in
(newL := CELL{left = l, right = r, data = f data};
newL)
end
| SOME newL => newL
)
in
copy (rightDlist (leftDlist d)) nil
end
fun copyDlist d = mapDlist (fn x => x) d
fun foldrDlist F z d =
let
fun member x nil = false
| member x (h::t) = x = h orelse member x t
fun f d z visited =
if member d visited then z
else F (dataDlist d, f (rightDlist d) z (d::visited))
in f (rightDlist (leftDlist d)) z nil
end
fun foldlDlist F z d =
let
fun member x nil = false
| member x (h::t) = x = h orelse member x t
fun f d z visited =
if member d visited then z
else f (rightDlist d) (F (dataDlist d, z)) (d::visited)
in f (rightDlist (leftDlist d)) z nil
end