プログラミング言語 Standard ML 入門 (問題の解答例)
10.4 モジュールを使ったプログラミング例
問 10.6
以下の実行結果を予測せよ．
BF.bf (fromPreOrder "1(2(3()())(4()()))(5()())");
さらに，実際にテストを行い，結果を確認せよ．
解答例 幅優先探索であるから、ルートから同一レベルのルートが順に探索される。 従って、1,2,5,3,4の順に探索されるはずである。 実際、SML#での実行結果は以下の通りである。
# BF.bf (fromPreOrder "1(2(3()())(4()()))(5()())"); val a = ["1", "2", "5", "3", "4"] : string list
問 10.7
解答例 ITQueue、 BFI、 fromIntPreOrxder の定義例を以下に示す。
structure ITQueue :> POLY_QUEUE where type elem = int tree =
struct
exception EmptyQueue
type elem = int tree
type queue = elem list ref * elem list ref
fun newQueue () = (ref [],ref []) : queue
fun enqueue (i,(a,b)) = a := i :: (!a)
fun dequeue (ref [],ref []) = raise EmptyQueue
| dequeue (a as ref L, b as ref []) =
let val (h::t) = rev L
in (a:=nil; b:=t; h)
end
| dequeue (a,b as ref (h::t)) = (b := t; h)
end
structure BFI = struct
structure Q = ITQueue
fun bf t =
let val queue = Q.newQueue()
fun loop () =
(case Q.dequeue queue of
Node(data,l,r) => (Q.enqueue (l,queue);
Q.enqueue (r,queue);
data::loop())
| Empty => loop())
handle Q.EmptyQueue => nil
in (Q.enqueue (t,queue); loop())
end
end
fun fromIntPreOrder s =
if s = "" then Empty
else let val (root,left,right) = decompose s
val SOME data = Int.fromString root
in Node(data, fromIntPreOrder left, fromIntPreOrder right)
end
SML#によるBFI.bfのテスト結果は以下の通りである。
# val intList = BFI.bf (fromIntPreOrder "1(2(3()())(4()()))(5()())"); val intList = [1, 2, 5, 3, 4] : int list
問 10.8
string tree を要素とする待ち行列を， 関数型待ち行列による方法，および， 単純なリストによる実現法 の2通りの方法で定義し，それぞれに対してBFのQストラクチャの定義 を変更し，いずれの場合も BF が正しく動くことを確かめよ．
解答例 それぞれのBFの定義例を以下にしめす。 以下では、単純なリストの場合のストラクチャ名をBFSimpleとしてある。
structure STQueue :> POLY_QUEUE where type elem = string tree = struct
exception EmptyQueue
type elem = string tree
type queue = elem list ref * elem list ref
fun newQueue () = (ref [],ref []) : queue
fun enqueue (i,(a,b)) = a := i :: (!a)
fun dequeue (ref [],ref []) = raise EmptyQueue
| dequeue (a as ref L, b as ref []) =
let val (h::t) = rev L
in (a:=nil; b:=t; h)
end
| dequeue (a,b as ref (h::t)) = (b := t; h)
end
structure BF = struct
structure Q = STQueue
fun bf t =
let val queue = Q.newQueue()
fun loop () =
(case Q.dequeue queue of
Node(data,l,r) => (Q.enqueue (l,queue);
Q.enqueue (r,queue);
data::loop())
| Empty => loop())
handle Q.EmptyQueue => nil
in (Q.enqueue (t,queue); loop())
end
end
structure STQueueSimple :> POLY_QUEUE where type elem = string tree = struct
exception EmptyQueue
type elem = string tree
type queue = elem list ref
fun newQueue() = ref nil : queue
fun enqueue (item,queue) =
queue := item :: (!queue)
fun removeLast nil = raise EmptyQueue
| removeLast [x] = (nil,x)
| removeLast (h::t) =
let val (t’,last) = removeLast t
in (h::t’,last)
end
fun dequeue queue =
let val (rest,last) = removeLast (!queue)
in (queue:=rest; last)
end
end
structure BFSimple = struct
structure Q = STQueueSimple
fun bf t =
let val queue = Q.newQueue()
fun loop () =
(case Q.dequeue queue of
Node(data,l,r) => (Q.enqueue (l,queue);
Q.enqueue (r,queue);
data::loop())
| Empty => loop())
handle Q.EmptyQueue => nil
in (Q.enqueue (t,queue); loop())
end
end
SML#によるテスト実行結果は以下の通りである。
# val a = BF.bf (fromPreOrder "1(2(3()())(4()()))(5()())"); val a = ["1", "2", "5", "3", "4"] : string list # val b = BFSimple.bf (fromPreOrder "1(2(3()())(4()()))(5()())"); val b = ["1", "2", "5", "3", "4"] : string list
問 10.9
BF ストラクチャに，以下の引数を受け取り結果を返す汎用な関数 bffold の定義を追加せよ．
-
1.
木が空のとき返す値
-
2.
空でない木に対して，ルートノードのデータと， ルート以外のノードを幅優先でたどり処理した結果を受け取り，最終結果を返す関数．
BF ストラクチャの bf 関数をごくわずか変更するだけで， 簡単に定義できるはずである．
bffold は，上記の関数 bf とリストの foldr 関数を組み 合わせて得られる関数と同一の動きをするはずである． 以下の2つの関数が同一の動作をすることをテストによって確かめよ．
-
•
BF.bffold f z t
-
•
foldr f z (BF.bf t)
解答例 bffoldを含むBFの定義例を示す。 bfとbffoldはほぼ同一の構造をもち、かつ前者は後者を使って簡単に定義できるため、 以下の例では、bfの定義をbffoldを使って定義してある。
structure BF = struct
structure Q = STQueue
fun bffold f z t =
let val queue = Q.newQueue()
fun loop () =
(case Q.dequeue queue of
Node(data,l,r) => (Q.enqueue (l,queue);
Q.enqueue (r,queue);
f (data, loop()))
| Empty => loop())
handle Q.EmptyQueue => z
in (Q.enqueue (t,queue); loop())
end
fun bf t = bffold (op ::) nil t
end
以下は、SML#によるテスト例である。
# val a = BF.bf (fromPreOrder "1(2(3()())(4()()))(5()())"); val a = ["1", "2", "5", "3", "4"] : string list # val b = BF.bffold (op ::) nil (fromPreOrder "1(2(3()())(4()()))(5()())"); val b = ["1", "2", "5", "3", "4"] : string list # val c = BF.bffold (op ^) "" (fromPreOrder "1(2(3()())(4()()))(5()())"); val c = "12534" : string # val d = foldr (op ^) "" (BF.bf (fromPreOrder "1(2(3()())(4()()))(5()())")); val d = "12534" : string