10.1 Structure文によるモジュールの定義と利用

問 10.1

第8.3節で定義した循環2重リストを使い， IntQueue と置き換え可能なストラクチャ ImperativeIntQueue を定義し，そのテストを行え．

解答例この例を実装するために、まず、循環2重リストのコードを以下のDListストラクチャにまとめる。

   structure DList =
   struct
     datatype ’a cell
       = NIL
       | CELL of {data:’a, left:’a cell ref, right:’a cell ref}
     exception EMPTY_DLIST
     type ’a dlist = ’a cell ref
     fun emptyDlist () = ref NIL
     fun rightDlist (ref (CELL{right,...})) = right | rightDlist _ = raise EMPTY_DLIST
     fun leftDlist (ref (CELL{left,...})) = left | leftDlist _ = raise EMPTY_DLIST
     fun dataDlist (ref (CELL{data,...})) = data | dataDlist _ = raise EMPTY_DLIST
     fun singleton a =
         let
           val l = ref NIL
           val r = ref NIL
           val c = CELL{left=l, right=r, data=a}
         in  (l:=c; r:=c; ref c)
         end
     fun member x nil = false
       | member x (h::t) = x = h orelse member x t
     fun insert a dlist =
         case dlist of
           ref (CELL{left=l1 as ref (CELL{right=r1,...}),...}) =>
           let val newcell = CELL{data=a,
                                  right=ref (!dlist),
                                  left=ref (!l1)}
           in (dlist:=newcell; l1:=newcell; r1:=newcell)
           end
         | ref NIL =>
           let
             val l = ref NIL
             val r = ref NIL
             val cell = CELL{data=a,left=l,right=r}
           in  (dlist:=cell; l:=cell; r:=cell)
           end
         | _ => raise EMPTY_DLIST
   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 toList L =
         let fun f l visited =
                 if member l visited then nil
                 else (dataDlist l)::(f (rightDlist l) (l::visited))
         in f (rightDlist (leftDlist L)) nil
         end
     fun fromList (L:int list) = foldl (fn (x,y) => (insert x y;y)) (ref NIL) L
     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
         | _ => raise EMPTY_DLIST
     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 d nil
         end
     fun copyDlist d = mapDlist (fn x => x) d
     fun foldrDlist F z d =
         let
           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 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
   end

ImperativeIntQueueストラクチャは、このDListストラクチャを使って、以下のように定義される。

   structure ImperativeIntQueue =
   struct
     exception EmptyQueue
     type queue = int DList.dlist
     fun newQueue() = DList.emptyDlist() : queue
     fun enqueue (item,queue) = DList.insert item queue
     fun dequeue queue =
         let
           val last = DList.leftDlist queue
           val data = DList.dataDlist last
         in
           (DList.deleteDlist last; data)
         end
         handle DList.EMPTY_DLIST => raise EmptyQueue
   end

以下は、実行結果である。

   # val q = ImperativeIntQueue.newQueue();
   val q = ref NIL : int DList.cell ref
   # val _ = ImperativeIntQueue.enqueue(1,q);
   # val x = ImperativeIntQueue.dequeue q;
   val x = 1 : int

問 10.2

FastIntQueue が正しく待ち行列を実現していることを確認せよ．すなわち，空の待ち行列から始めて enqueue と dequeue 操作を繰り返したときの動作が，単純なリストによる場合と同一であることを示せ．

解答例空の待ち行列から始めてenqueue(Q, $e_{i}$ )を $n$ 回、 dequeueを $m\ (n>m)$ 実施した場合を考える。単純なリストの場合、リストの中身は、 $[e_{n},e_{n-1},\ldots,e_{n-m}]\ (n>m))$ であり、次のdequeue操作で、 $e_{n-m}$ が返される。任意の $n,m(n>m)$ について、FastQueueの場合も、この状態と同等の状態が保たれることが示せればよい。 FastIntQueueの操作途中の状態は、２つのリストの組 $(L1,L2)$ である。この２つのリストの中の要素を

\begin{array}[]{lcl}L1&=&[e_{1}^{1},\ldots,e_{n}^{1}]\\ L2&=&[e_{1}^{2},\ldots,e_{n}^{2}]\end{array}

とする。すると、

[e_{1}^{1},\ldots,e_{n}^{1},e_{n}^{2},\ldots,e_{1}^{2}]=[e_{n},e_{n-1},\ldots,% e_{n-m}]

が成立し、次に返される値 $e_{1}^{2}$ は、 $e_{n-m}$ であり、リストを用いた待ち行列と同一である。この性質が、任意の $n,m(n>m)$ で成り立つから、 FastQueueは単純なリストを用いた実装と同一の振る舞いをする。

問 10.3

enqueue と dequeue がランダムに行われる場合の，dequeue の平均の実行時間を見積もれ．

解答例 dequeueに掛かる実行時間を

1.

リストに要素を１つ追加するための必要な時間 $C O N S$
2.

リストから先頭要素を１つ取り出すのに必要な時間 $C A R$

の回数で見積もる。 $L_{2}$ が空でない合は $CAR=1,CONS=0$ である。 $L_{2}$ が空の場合、 $L_{1}$ の長さを $N$ とすると、 $CAR=N+1,CONS=N$ に等しく、これら回数の平均を見積もることである。

この問題は、amortize cost（償却原価）の考え方を使えば、統計的・解析的な計算をせず、即座に求めることができる。 dequeueで取り除かれる要素 $e$ に着目する。この要素は、enqueueで $L1$ のリストの先頭に追加され、さらに、dequeue操作でとりだされる前のいずれかのdequeue操作で $L1$ のリストから取り除かれ、 $L2$ のリストの先頭に追加される。このコストは $CAR=1,CONS=1$ である。そこで、この $e$ が待ち行列に追加された時、この要素を dequeueするための将来必要なコスト原価として計上しておく、と考える。すると、dequeue操作では、 $L2$ が空の時に、 $L1$ から $L2$ へ移動させるコストはすでにこの原価に含まれている、と考え、取り除かれる要素 $e$ のコストは、 $e$ を取り除くための原価( $CAR=1,CONS=1$ ) ＋実際に掛かるコスト（ $CAR=1$ ）と計算できる。以上から、dequeue操作の平均時間は $CAR=2,CONS=1$ である。

ちなみに、enqueue操作の平均時間は、 $CONS=1$ であるから、 FastQueueの要素あたりのenqueue、dequeueコストは $CONS=2,CAR=2$ であることがわかる。

問 10.4

IntQueue をFastIntQueue に置き換えてテストを行え．

解答例教科書にあるコードの通りIntQueueが定義されている環境で、たとえば、以下のようなコードが可能である。

   structure Q = IntQueue
   val q = Q.newQueue()
   val _ = Q.enqueue(1, q)
   val _ = Q.enqueue(2, q)
   val _ = Q.enqueue(3, q)
   val a = Q.dequeue q
   val b = Q.dequeue q
   val c = Q.dequeue q

SML#の対話型環境では、以下のような実行結果を得る。

   # structure Q = IntQueue;
   structure Q =
     struct
       type queue = int list ref
       exception EmptyQueue = IntQueue.EmptyQueue
       val newQueue = fn : unit -> int list ref
       val enqueue = fn : [’a. ’a * ’a list ref -> unit]
       val removeLast = fn : [’a. ’a list -> ’a list * ’a]
       val dequeue = fn : [’a. ’a list ref -> ’a]
     end
   # val q = Q.newQueue();
   val q = ref [] : int list ref
   # val _ = Q.enqueue(1, q);
   # val _ = Q.enqueue(2, q);
   # val _ = Q.enqueue(3, q);
   # val a = Q.dequeue q;
   val a = 1 : int
   # val b = Q.dequeue q;
   val b = 2 : int
   # val c = Q.dequeue q;
   val c = 3 : int
   #

このQストラクチャの定義のみを、FastIntQueueに置き換えると以下のコードを得る。

   structure Q = FastIntQueue
   val q = Q.newQueue()
   val _ = Q.enqueue(1, q)
   val _ = Q.enqueue(2, q)
   val _ = Q.enqueue(3, q)
   val a = Q.dequeue q
   val b = Q.dequeue q
   val c = Q.dequeue q

SML#の対話型環境では、以下のような実行結果を得る。

   # structure Q = FastQueue;
   structure Q =
     struct
       type elem = int32
       type queue = elem list ref * elem list ref
       exception EmptyQueue = FastQueue.EmptyQueue
       val newQueue = fn : unit -> elem list ref * elem list ref
       val enqueue = fn : [’a, ’b. ’a * (’a list ref * ’b) -> unit]
       val dequeue = fn : [’a. ’a list ref * ’a list ref -> ’a]
     end
   # val q = Q.newQueue();
   val q = (ref [], ref []) : int list ref * int list ref
   # val _ = Q.enqueue(1, q);
   # val _ = Q.enqueue(2, q);
   # val _ = Q.enqueue(3, q);
   # val a = Q.dequeue q;
   val a = 1 : int
   # val b = Q.dequeue q;
   val b = 2 : int
   # val c = Q.dequeue q;
   val c = 3 : int

この結果から、同一の動作をしており、置き換え可能であることが確認できる。