プログラミング言語 Standard ML 入門 (問題の解答例)
10.5 functor文を使ったモジューラープログラミング
問 10.10
上記の QueueFUN を完成し，それを使って STQueue と ITQueue を定義せよ．
さらに，それらを定義の下で，BF ストラクチャおよび BFI ストラクチャを作成しなおし，
BF.bf (fromPreOrder "1(2(3()())(4()()))(5()())");
BFI.bf (fromIntPreOrder "1(2(3()())(4()()))(5()())");
などのテストプログラムを実行し，正しく動くことを確かめよ．
解答例 コード例を以下に示す。
functor QueueFUN(type ty) :> POLY_QUEUE where type elem = ty =
struct
exception EmptyQueue
type elem = ty
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 ITQueue = QueueFUN(type ty = int tree)
structure STQueue = QueueFUN(type ty = string tree)
structure BF = struct
structure Q = STQueue
fun bf t =
let val queue = Q.newQueue()
fun loop () =
(case Q.dequeue queue of
Node(data,r,l) => (Q.enqueue (r,queue);
Q.enqueue (l,queue);
data::loop())
| Empty => loop())
handle Q.EmptyQueue => nil
in (Q.enqueue (t,queue); loop())
end
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
以下は、SML#によるテスト例である。
# val a = BF.bf (fromPreOrder "1(2(3()())(4()()))(5()())"); val a = ["1", "2", "5", "3", "4"] : string list # val b = BFI.bf (fromIntPreOrder "1(2(3()())(4()()))(5()())"); val b = [1, 2, 5, 3, 4] : int list
問 10.11
種々の要素の型に対する待ち行列を作成するもう1つの方法は， 待ち行列を ’a queue のような多相型にすることである． しかし多相型を持つ値に対する参照は許されない． そこで，参照型を使わずに，待ち行列のシグネチャを以下のように変更 することにする．
signature FUNQUEUE = sig
type ’a queue
val newQueue : unit -> ’a queue
val enqueue : ’a * ’a queue -> ’ a queue
val dequeue : ’a queue -> ’a * ’a queue
end
IntQueue および FastIntQueue を それぞれこのシグネチャを持つように変更し，汎用の待ち行列ストラクチャを作 成せよ．
解答例 以下にコード例を示す。このコードでは、FUNQUEUEシグネチャに EmptyQueue例外を追加してある。 また、汎用の待ち行列名をそれぞれQueue、FastQueueとし 不透明なシグネチャ制約を付してある。
signature FUNQUEUE = sig
type ’a queue
exception EmptyQueue
val newQueue : unit -> ’a queue
val enqueue : ’a * ’a queue -> ’a queue
val dequeue : ’a queue -> ’a * ’a queue
end
structure Queue :> FUNQUEUE =
struct
exception EmptyQueue
type ’a queue = ’a list
fun newQueue() = nil : ’a queue
fun enqueue (item,queue) = item :: queue
fun dequeue nil = raise EmptyQueue
| dequeue [x] = (x, nil)
| dequeue (h::t) =
let val (last, t’) = dequeue t
in (last, h::t’)
end
end
structure FastQueue :> FUNQUEUE = struct
exception EmptyQueue
type ’a queue = ’a list * ’a list
fun newQueue () = ([],[]) : ’a queue
fun enqueue (i,(a,b)) = (i :: a, b)
fun dequeue ([],[]) = raise EmptyQueue
| dequeue (L, []) =
let
val (h::t) = rev L
in
(h, ([], t))
end
| dequeue (a,h::t) = (h, (a,t))
end
以下は、SML#によるテスト例である。
# val q = Queue.newQueue() : int Queue.queue; val q = _ : int Queue.queue # val q = Queue.enqueue(1, q); val q = _ : int Queue.queue # val q = Queue.enqueue(2, q); val q = _ : int Queue.queue # val q = Queue.enqueue(3, q); val q = _ : int Queue.queue # val (a,q) = Queue.dequeue q; val a = 1 : int val q = _ : int Queue.queue # val (b,q) = Queue.dequeue q; val b = 2 : int val q = _ : int Queue.queue # val (c,q) = Queue.dequeue q; val c = 3 : int val q = _ : int Queue.queue # val q’ = FastQueue.newQueue() : int FastQueue.queue; val q’ = _ : int FastQueue.queue # val q’ = FastQueue.enqueue(4, q’); val q’ = _ : int FastQueue.queue # val q’ = FastQueue.enqueue(5, q’); val q’ = _ : int FastQueue.queue # val q’ = FastQueue.enqueue(6, q’); val q’ = _ : int FastQueue.queue # val (d,q’) = FastQueue.dequeue q’; val d = 4 : int val q’ = _ : int FastQueue.queue # val (e,q’) = FastQueue.dequeue q’; val e = 5 : int val q’ = _ : int FastQueue.queue # val (f,q’) = FastQueue.dequeue q’; val f = 6 : int val q’ = _ : int FastQueue.queue
問 10.12
入出力バッファを生成するファンクタの定義を， FUNQUEUE シグネチャを持つストラクチャを受け取り BUFFER シグネチャを持つストラクチャを生成するように変更せよ．
解答例 以下にコード例を示す。
functor BufferFUN(structure FQueue : FUNQUEUE )
:> BUFFER =
struct
exception EndOfBuffer
type channel = char FQueue.queue ref
fun openBuffer () = ref (FQueue.newQueue()) : channel
fun input ch =
let
val (out, queue) = (FQueue.dequeue (!ch))
in
(ch := queue; out)
end
handle FQueue.EmptyQueue => raise EndOfBuffer
fun output(ch, c) = ch := FQueue.enqueue (c, !ch)
end