Answers to Exercises for Chapter 7

**7.1.** It is quadratic in *n*. Calling `enq(q,x)`costs length(q)+1 cons operations. We get the recurrence equations T(0)=0 and T(n+1) = n+1+T(n). The solution is T(n) = n(n+1)/2.

**7.2.** The first representation gives quick access to the front of the queue, while the second one gives quick access to the rear. Neither point is much of an advantage, since in normal use the front and rear are used equally often. With Representation 1, `deq` takes constant time, but with Representation 3, it occasionally takes time linear in the length of the queue. Representation 1 can only be more efficient than Representation 3 if usage is non-single-threaded: that is, if the result of `deq` is discarded instead of taken as the new queue.

**7.3.**

structure Queue2a = struct type 'a t = 'a list; exception E; val empty = []; fun enq(q,x) = x::q; fun null(x::q) = false | null [] = true; fun hd [x] = x | hd (_::q) = hd q | hd [] = raise E; fun deq [x] = [] | deq (x::q) = x :: deq q | deq [] = raise E; end;

**7.4.** Note that the head is always stored at subscript 0 because `lorem` shifts down the array elements. With this version, each operation takes logarithmic time in the length of the queue, while occasionally Representation 3 can require linear time for a single `deq` operation. However, over the lifetime of a queue, Representation 3 will be more efficient, since virtually all operations will take constant time.

structure Queue4 = struct type 'a t = 'a Flex.array; exception E; val empty = Flex.empty; fun enq(q, x) = Flex.hiext(q,x); fun null(q) = (Flex.length q = 0); fun hd q = Flex.sub(q,0) handle Subscript => raise E; fun deq q = Flex.lorem(q) handle Size => raise E; end;

**7.5.** If an upper bound on the length of the queue is fixed in advance then ordinary functional arrays can be used to replace imperative arrays. However, having to fix the bound is unattractive when the other representations allow unbounded queues. If instead we allow the first and last subscripts to grow indefinitely, then functional arrays will become increasingly inefficient. The flexible array approach (above) would be better.

**7.7.** Signature `QUEUE` gains two additional lines. Note the equality type variables in the type of `equals`.

val length: 'a t -> int (*length of queue*) val equal: ''a t * ''a t -> bool (*equality between queues*)Two lines are added to

val length = List.length; fun equal(q1, q2) = (q1=q2);For

fun length (enq(q,_)) = length q + 1 | length empty = 0;For

fun equal(q1,q2) = (q1=q2);

fun length (Queue(heads,tails)) = List.length heads + List.length tails; fun equal(Queue(heads1,tails1),Queue(heads2,tails2)) = heads1 @ rev tails1 = heads2 @ rev tails2;

**7.8.** The two representations are lists and a new datatype. Exception handling is omitted.

abstype 'a stack1 = S1 of 'a list with val empty = S1 []; fun push(x, S1 st) = S1 (x::st); fun snull(S1(x::st)) = false | snull _ = true; fun top(S1(x::st)) = x; fun pop(S1(x::st)) = S1 st; end; abstype 'a stack2 = Empty | Push of 'a * 'a stack2 with val empty = Empty and push = Push fun snull (Push _) = false | snull Empty = true; fun top (Push(x,st)) = x; fun pop (Push(x,st)) = st; end;

**7.9.** First, here is the `abstype` declaration.

abstype rat = Rat of int*int with local fun gcd(m,n) = if m=0 then n else gcd(n mod m, m); fun canon (m,n) = let val d = gcd(abs m, n) in Rat (m div d, n div d) end fun recip (Rat(m,n)) = if m<0 then Rat(~n,~m) else Rat(n,m) in val rat_zero = Rat(0, 1); fun rat_sum (Rat(m,n), Rat(m',n')) = canon(m*n' + m'*n, n*n'); fun rat_diff (Rat(m,n), Rat(m',n')) = canon(m*n' - m'*n, n*n'); fun rat_prod (Rat(m,n), Rat(m',n')) = canon(m*m', n*n'); fun rat_quo (x,x') = rat_prod(x, recip x'); end end;

This version replaces the `local` declaration with signature matching.

structure Rational : ARITH = struct abstype t = Rat of int*int with fun gcd(m,n) = if m=0 then n else gcd(n mod m, m); fun canon (m,n) = let val d = gcd(abs m, n) in Rat (m div d, n div d) end fun recip (Rat(m,n)) = if m<0 then Rat(~n,~m) else Rat(n,m) val zero = Rat(0, 1); fun sum (Rat(m,n), Rat(m',n')) = canon(m*n' + m'*n, n*n'); fun diff (Rat(m,n), Rat(m',n')) = canon(m*n' - m'*n, n*n'); fun prod (Rat(m,n), Rat(m',n')) = canon(m*m', n*n'); fun quo (x,x') = prod(x, recip x'); end end;

**7.10.**

abstype date = D of int * int with local val months = [31,28,31,30,31,30,31,31,30,31,30,31]; fun days m = List.nth (months, m-1); fun date_ok (d,m) = 1 <= m andalso m <= 12 andalso 1 <= d andalso d <= days m; in exception Date; fun today (d,m) = if date_ok (d,m) then D(d,m) else raise Date; fun day (D(d,m)) = d and month (D(d,m)) = m; fun tomorrow (D(d,m)) = if date_ok (d+1,m) then D(d+1,m) else if m<12 then D(1,m+1) else raise Date; fun yesterday (D(d,m)) = if date_ok (d-1,m) then D(d-1,m) else if m>1 then D(days (m-1), m-1) else raise Date; end end;

**7.11.** Structure `Queue2a` from the solution to **7.3** has that signature.

**7.12.** For example, modify `Queue1` to have the following definition of `enq`. The resulting structure implements a stack rather than a queue.

fun enq(q,x) = q @ [x];

**7.13.** This exercise is up to you. Java is a suitable language to choose because modularity can be expressed using objects.

**7.14.** It is very poor because it only tests one pattern of usage, where all calls to `enq` come before all calls to `deq`.

**7.15.** The trick is to use type `option`.

structure PathZSP = struct type t = int option; val zero = NONE; fun sum (SOME m, SOME n) = SOME (Int.min(m,n)) | sum (NONE, on) = on | sum (om, NONE) = om fun prod (SOME m, SOME n) = SOME (m+n) : t | prod _ = NONE end;

**7.16**. Vectors are related to Basis Library arrays, which are introduced in Section 8.6.

functor VMatrixZSP (Z: ZSP) : ZSP = let open Vector in struct type t = Z.t vector vector; val zero = fromList []; fun sum (rowvA,rowvB) = if length rowvA = 0 then rowvB else if length rowvB = 0 then rowvA else tabulate (length rowvA, fn i => let val rowA = sub(rowvA,i) and rowB = sub(rowvB,i) in tabulate (length rowA, fn j => Z.sum (sub (rowA,j), sub (rowB,j))) end); fun prod (rowvA,rowvB) = if length rowvA = 0 orelse length rowvB = 0 then zero else tabulate (length rowvA, fn i => let val rowA = sub(rowvA,i) in tabulate (length (sub(rowvB,0)), fn j => let fun adding k = if k<0 then Z.zero else Z.sum (adding (k-1), Z.prod (sub(rowA,k), sub(sub(rowvB,k),j))) in adding (length rowA - 1) end) end); end end;

**7.17**. The abstype constructor, called `D` below, complicates the code slightly and necessitates separating the external versions of `insert` and `update` from the ones that do the actual work.

functor Dictionary (Key: ORDER) : DICTIONARY = struct type key = string; abstype 'a t = D of (key * 'a) list with exception E of key; val empty = D[]; fun lookup (D((a,x)::pairs), b) = (case String.compare(a,b) of GREATER => raise E b | EQUAL => x | LESS => lookup(D pairs, b)) | lookup (D [], b) = raise E b; fun inserting ((a,x)::pairs, b, y) = (case String.compare(a,b) of GREATER => (b,y)::(a,x)::pairs | EQUAL => raise E b | LESS => (a,x)::inserting(pairs, b, y)) | inserting ([], b, y) = [(b,y)]; fun insert (D pairs, b, y) = D (inserting (pairs, b, y)); fun updating ((a,x)::pairs, b, y) = (case String.compare(a,b) of GREATER => (b,y)::(a,x)::pairs | EQUAL => (b,y)::pairs | LESS => (a,x)::updating(pairs, b, y)) | updating ([], b, y) = [(b,y)]; fun update (D pairs, b, y) = D (updating (pairs, b, y)); end end;

**7.18**. Declaring fresh constructors lets us copy the binary tree code into the `abstype` body.

abstype t = Lf | Br of Item.t * t * t with val empty = Lf; fun null Lf = true | null (Br _) = false; fun min (Br(v,_,_)) = v; fun insert(w, Lf) = Br(w, Lf, Lf) | insert(w, Br(v, t1, t2)) = if w <= v then Br(w, insert(v, t2), t1) else Br(v, insert(w, t2), t1); fun leftrem (Br(v,Lf,_)) = (v, Lf) | leftrem (Br(v,t1,t2)) = let val (w, t) = leftrem t1 in (w, Br(v,t2,t)) end; fun siftdown (w, Lf, _) = Br(w,Lf,Lf) | siftdown (w, t as Br(v,_,_), Lf) = if w <= v then Br(w, t, Lf) else Br(v, Br(w,Lf,Lf), Lf) | siftdown (w, t1 as Br(v1,p1,q1), t2 as Br(v2,p2,q2)) = if w <= v1 andalso w <= v2 then Br(w,t1,t2) else if v1 <= v2 then Br(v1, siftdown(w,p1,q1), t2) (* v2 < v1 *) else Br(v2, t1, siftdown(w,p2,q2)); fun delmin Lf = raise Size | delmin (Br(v,Lf,_)) = Lf | delmin (Br(v,t1,t2)) = let val (w,t) = leftrem t1 in siftdown (w,t2,t) end; fun heapify (0, vs) = (Lf, vs) | heapify (n, v::vs) = let val (t1, vs1) = heapify (n div 2, vs) val (t2, vs2) = heapify ((n-1) div 2, vs1) in (siftdown (v,t1,t2), vs2) end; fun fromList vs = #1 (heapify (length vs, vs)); fun toList (t as Br(v,_,_)) = v :: toList(delmin t) | toList Lf = []; fun sort vs = toList (fromList vs); end

A dummy constructor allows existing code for binary trees to be invoked. The `abstype` body looks something like this.

abstype t = PQ of Item.t tree with val empty = PQ Lf; fun null (PQ Lf) = true | null _ = false; fun min (PQ(Br(v,_,_))) = v; fun insert'(w, Lf) = Br(w, Lf, Lf) | insert'(w, Br(v, t1, t2)) = if w <= v then Br(w, insert'(v, t2), t1) else Br(v, insert'(w, t2), t1); fun insert (w, PQ t) = PQ (insert' (w, t)); ... end

**7.19**. Needless to say, increasing lists are inherently inefficient. Insertions can take linear time.

functor PriorityQueue (Item: ORDER) : PRIORITY_QUEUE = struct structure Item = Item; fun x <= y = (Item.compare(x,y) <> GREATER); abstype t = PQ of Item.t list with val empty = PQ []; fun null (PQ vs) = List.null vs; fun min (PQ(v::_)) = v; fun insert'(w, []) = [w] | insert'(w, v::vs) = if w <= v then w::v::vs else v :: insert'(w,vs); fun insert (w, PQ t) = PQ (insert' (w, t)); fun delmin (PQ []) = raise Size | delmin (PQ (v::vs)) = PQ vs; fun fromList' [] = [] | fromList' (w::ws) = insert' (w, fromList' ws); fun fromList vs = PQ (fromList' vs); fun toList (PQ vs) = vs; fun sort vs = toList (fromList vs); end end;

**7.20**. Existing sorting functions can be dropped right into the functor body. Then replace references to specific types (originally `real`) by the type of sorting function supplied in the functor argument, namely `Item.t`. The functor body defines its own version of `<=` for use in the sorting functions. The advantage of implementing two sorting functions is that each has its merits. However, it would actually be better to provide two separate functors. That would be more modular, allowing each to be maintained separately.

functor Sorting (Item: ORDER) = struct fun x <= y = (Item.compare(x,y) <> GREATER); fun quick [] = [] | quick [x] = [x] | quick (a::bs) = (*the head "a" is the pivot*) let fun partition (left,right,[]) : Item.t list = (quick left) @ (a :: quick right) | partition (left,right, x::xs) = if x<=a then partition (x::left, right, xs) else partition (left, x::right, xs) in partition([],[],bs) end; fun merge([],ys) = ys : Item.t list | merge(xs,[]) = xs | merge(x::xs, y::ys) = if x<=y then x::merge(xs, y::ys) else y::merge(x::xs, ys); fun tmergesort [] = [] | tmergesort [x] = [x] | tmergesort xs = let val k = length xs div 2 in merge (tmergesort (List.take(xs,k)), tmergesort (List.drop(xs,k))) end; end;

**7.21.** This solution relies on the convention that multiple arguments in a functor heading are regarded as implicitly defining a signature. We could instead have defined a signature, say EQTYPE, specified by those arguments.

functor AssocList (type key; val eq: key*key -> bool) : DICTIONARY = struct type key = key; exception E of key; abstype 'a t = Nil | Cons of key * 'a * 'a t with val empty = Nil; fun lookup (Cons(a,x,al), b) = if eq(a,b) then x else lookup(al, b) | lookup (Nil, b) = raise E b; fun insert (Cons(a,x,al), b, y) = if eq(a,b) then raise E b else Cons (a, x, insert(al, b, y)) | insert (Nil, b, y) = Cons(b,y,Nil); fun update (al, b, y) = Cons(b,y,al) end end;

**7.22.** This version defines new constructors in order to avoid the annoyance of programming with a dummy constructor.

functor AssocList (eqtype key) : DICTIONARY = struct type key = key; exception E of key; abstype 'a t = Nil | Cons of key * 'a * 'a t with val empty = Nil; fun lookup (Cons(a,x,al), b) = if a=b then x else lookup(al, b) | lookup (Nil, b) = raise E b; fun insert (Cons(a,x,al), b, y) = if a=b then raise E b else Cons (a, x, insert(al, b, y)) | insert (Nil, b, y) = Cons(b,y,Nil); fun update (al, b, y) = Cons(b,y,al) end end;

**7.23.** The lexicographic ordering compares the second components only if the first components are equal.

signature PORDER = sig type t val compare: t*t -> order option end; functor LexPOrder (structure PO1: PORDER and PO2: PORDER) : PORDER = struct type t = PO1.t * PO2.t; fun compare ((x1,y1), (x2,y2)) = (case PO1.compare (x1,x2) of SOME EQUAL => PO2.compare (y1,y2) | ord => ord) end;

**7.24.** This ordering is an inverse image construction. If `f(x)=f(y)` then we must regard `x` and `y` as unrelated.

functor InvPOrder (type t; structure PO: PORDER; val f: t -> PO.t) : PORDER = struct type t = t; fun compare (x,y) = (case PO.compare (f x, f y) of SOME EQUAL => NONE | ord => ord) end;

**7.25.** All structures are instances of the empty signature.

**7.26.** ML accepts the declarations of signature `TYPE` and functor `Funny`, whose two arguments are required to share. The declarations of structures `S1` and `S2` are also acceptable. Now `S1=DT1` and `S2=DT2`. Because `S1` and `S2` denote distinct structures, namely `DT1` and `DT2`, respectively, the attempted declaration of `S3` fails due to a violation of the functor's sharing constraint.

**7.27.** These declarations are correct.

structure In = Inputs (structure PQueue = StringPQueue) and Out = Outputs (structure PQueue = StringPQueue); structure System = Main (structure In = In and Out = Out);

However, if the call to `Inputs` instead supplied `IntegerPQueue`, the sharing constraint would be violated.

**7.28.** The sharing constraint will be violated: new abstract types never share.

**7.29.** It is identical to the structure declaration except in its first line.

functor Queue () : QUEUE = struct abstype 'a t = Queue of ('a list * 'a list) with exception E; val empty = Queue([],[]); ... fun deq(Queue(x::heads,tails)) = norm(Queue(heads,tails)) | deq(Queue([],_)) = raise E; end end;

**7.30.** Compared with the signature `SEQUENCE` presented in Chapter 5, the following signature includes a specification of the sequence type itself.

signature SEQUENCE = sig exception Empty type 'a seq val Nil : 'a seq val Cons : 'a * (unit -> 'a seq) -> 'a seq val cons : 'a * 'a seq -> 'a seq val null : 'a seq -> bool val hd : 'a seq -> 'a val tl : 'a seq -> 'a seq ... end; functor Sequence () :> SEQUENCE = struct exception Empty; datatype 'a seq = Nil | Cons of 'a * (unit -> 'a seq); fun hd (Cons(x,xf)) = x | hd Nil = raise Empty; fun tl (Cons(x,xf)) = xf() | tl Nil = raise Empty; fun cons(x,xq) = Cons(x, fn()=>xq); fun null (Cons _) = false | null Nil = true; ... end; functor Search (structure S : SEQUENCE and Q: QUEUE) = struct fun depthFirst next x = let fun dfs [] = S.Nil | dfs(y::ys) = S.Cons(y, fn()=> dfs(next y @ ys)) in dfs [x] end; (*enqueue a list of items*) fun enql (q, []) = q | enql (q, x::xs) = enql(Q.enq(q,x), xs); fun breadthFirst next x = let fun bfs q = if Q.null q then S.Nil else S.Cons(Q.hd q, fn()=> bfs(enql(Q.deq q, next(Q.hd q)))) in bfs (Q.enq(Q.empty, x)) end; end;

**7.31.** All of these signatures are self-contained.

`QUEUE1`: the types`bool`and`list``QUEUE2`: the type`bool``QUEUE3`: the types`bool`and`list``DICTIONARY`: none`FLEXARRAY`: the type`int`

**7.32.** Structure `UsedTwice` is given all the components of both arguments (which fortunately have no names in common) of functor `PriorityQueue` . Signature matching discards the surplus components.

**7.33.** The second `open` declaration hides most of `Queue3`'s components, except `norm`, which is not a component of `Queue2`.

**7.34.** The constant `2.0` has type `Real.real,` which differs from type `F.real`. We can create a version of the number 2 having the correct type by calling the function `F.fromInt`.

functor MultiplePrecision (F: REAL) = struct fun half x = F./(x, F.fromInt 2) end;

Last modified Monday, 3 September, 2007

Back to Exercises page