Elements of ML Programming, 2nd Edition (ML97)

Solutions for Chapter 8

Solutions for Section 8.2

Solutions for Section 8.2

Exercise 8.2.1

```     structure Tree = struct
exception Missing;

datatype 'label tree =
Node of 'label * 'label tree list;

(* create a one-node tree *)
fun create(a) = Node(a,nil);

(* build a tree from a label and a list of trees *)
fun build(a,L) = Node(a,L);

(* find the ith subtree of a tree *)
fun subtree(i,Node(a,nil)) = raise Missing
|   subtree(1,Node(a,t::ts)) = t
|   subtree(i,Node(a,t::ts)) = subtree(i-1,Node(a,ts));
end;
```

Exercise 8.2.2

An appropriate signature is:
```     signature SIMPLE = sig
exception Missing;
datatype 'label tree =
Node of 'label * 'label tree list;
val build : int * int tree list -> int tree;
val subtree : int * int tree -> int tree
end;
```
We can then use this signature to create the desired structure by
```     structure SimpleTree: SIMPLE = Tree;
```

Exercise 8.2.3

Here is one possible sequence of steps.
```     open SimpleTree;
val t2 = build(2,nil);
val t3 = build(3,nil);
val t1 = build(4,nil);
val t4 = build(1,[t1,t2,t3]);
subtree(2,t4);
```

Exercise 8.2.6

```     structure Queue = struct
exception EmptyQueue;

type 'a queue = 'a list;

val create = nil;

fun enqueue(x,Q) = Q@[x];

fun dequeue(nil) = raise EmptyQueue
|   dequeue(q::qs) = (q,qs);

fun isEmpty(nil) = true
|   isEmpty(_) = false;
end;
```
Note that we have written isEmpty as we did, rather than the more succinct fun isEmpty(Q) = (Q=nil), because by matching patterns we avoid the equality test and therefore allow the type of Q to be anything, even a non-equality type. Download this program

Solutions for Section 8.3

Exercise 8.3.2

```     signature SIM = sig
type element;
val sim : element * element -> bool
end;

functor MakeSimSet(Sim: SIM):
sig
type set;
val create : set;
val insert : Sim.element * set -> set;
val findSim : Sim.element * set -> set
end

=

struct
open Sim;
type set = element list;
val create = nil;
fun insert(x,S) = x::S;
fun findSim(x,nil) = nil
|   findSim(x,s::ss) =
if sim(x,s) then s::findSim(x,ss)
else findSim(x,ss)
end;

structure Misspell: SIM =
struct
type element = string;
fun sim("","") = true
|   sim("",_) = false
|   sim(_,"") = false
|   sim(x,y) =
let
val xs = implode(xtail);
val ys = implode(ytail)
in
else xs=ys
end
end;

structure MisspellSet =
MakeSimSet(Misspell);
```
Note that the code for function sim in structure Misspell will produce a warning because ML thinks that when we explode x and y, one or both could result in the empty list, which would not match the patterns like xhead::xtail. However, we have caught such cases in the preceding patterns that check for one or both strings being empty.

Solutions for Section 8.4

Exercise 8.4.1

Here is a possible structure called Pair with signature ELEMENT. We have chosen pairs of integers as the type element, and the function similar checks equality of the first components only.
```     structure Pair: ELEMENT  = struct
type element = int * int;
fun similar((x1,x2), (y1,y2)) = (x1=y1)
end;
```
Then, the following is a sketch of a structure that uses Pair as its substructure called Element and defines the local type elt to be the same type as appears in structure Pair.
```     structure BinaryTree: BTREE = struct
structure Element = Pair;
type elt = int * int;
(* suitable definitions for btree and the functions *)
end;
```
However, should we replace type elt = int * int in structure BinaryTree by any other type, for example type elt = real * int, then we would get an error indicating a violation of a sharing constraint.

Solutions for Section 8.5

Exercise 8.5.1

A solution appears below. To understand what is going on, note that in the datatype tttree the integer components are the separators, and the tttree components are the subtrees. Then, the datatype oneOrTwo either wraps one tree in S or two trees and a separator in P.

Function lookup is straightforward. We use the separators to guide us to the proper leaf. Function insert requires a lot of work. The heart is in a function insert1 that finds the proper subtree into which the insertion occurs and returns a oneOrTwo, that is, either a single tree or a pair, wrapped appropriately. The five auxiliary functions group test whether there is a single or a pair and produce a wrapped tree or pair, as appropriate. The only time a pair is produced is in the case where three subtrees become four, as was illustrated in Fig. 8.18 of the text. Note that the five group functions are named with a code where U stands for ``unknown'' (we get either a single or a pair) and T (we get a single tree).

```structure TTTree = struct
datatype tttree = Two of int * tttree * tttree |
Three of int * int * tttree * tttree * tttree |
Leaf of int;

datatype oneOrTwo = S of tttree |
P of int * tttree * tttree;

(* create(i) creates a 2-3 tree with one leaf,
labeled i *)
fun create(i) = Leaf(i);

(* lookup(x,T) tells whether integer x is at a leaf of
2-3 tree T *)
fun lookup(x,Leaf(i)) = (x=i)
|   lookup(x,Two(i,T1,T2)) =
if x=j *) lookup(x,T3);

(* the following 5 "group" functions are auxiliaries
used in the function insert1 below.
See explanation in the text. *)
fun groupUT(i,S(T1),T2) = S(Two(i,T1,T2))
|   groupUT(i,P(j,T1,T2),T3) = S(Three(j,i,T1,T2,T3));

fun groupTU(i,T1,S(T2)) = S(Two(i,T1,T2))
|   groupTU(i,T1,P(j,T2,T3)) = S(Three(i,j,T1,T2,T3));

fun groupUTT(i,j,S(T1),T2,T3) = S(Three(i,j,T1,T2,T3))
|   groupUTT(i,j,P(k,T1,T2),T3,T4) =
P(i,Two(k,T1,T2),Two(j,T3,T4));

fun groupTUT(i,j,T1,S(T2),T3) = S(Three(i,j,T1,T2,T3))
|   groupTUT(i,j,T1,P(k,T2,T3),T4) =
P(k,Two(i,T1,T2),Two(j,T3,T4));

fun groupTTU(i,j,T1,T2,S(T3)) = S(Three(i,j,T1,T2,T3))
|   groupTTU(i,j,T1,T2,P(k,T3,T4)) =
P(j,Two(i,T1,T2),Two(k,T3,T4));

(* insert1(x,T) inserts integer x into 2-3 tree T and
returns a oneOrTwo, that is, a 2-3 tree wrapped in S
or two 2-3 trees wrapped in P *)
fun insert1(x,Leaf(i)) =
if xi then P(x,Leaf(i),Leaf(x))
else S(Leaf(i))
|   insert1(x,Two(i,T1,T2)) =
if x=i *)
groupTU(i,T1,insert1(x,T2))
|   insert1(x,Three(i,j,T1,T2,T3)) =
if x=j *)
groupTTU(i,j,T1,T2,insert1(x,T3));

(* unwrap(X) either removes the one tree from an S or
creates a new node with the two subtrees found
inside a P. *)
fun unwrap(S(T)) = T
|   unwrap(P(i,T1,T2)) = Two(i,T1,T2);

(* insert(x,T) inserts x into 2-3 tree T. *)
fun insert(x,T) = unwrap(insert1(x,T))
end;
```

Exercise 8.5.5(a)

The user only needs to use the functions create, lookup, insert, and delete. All the other functions and the constant b can (and should) be hidden.

Exercise 8.5.5(b)

```structure SafeHash: sig
val create: unit -> string hashTable;
val lookup: string hashTable * string -> bool;
val insert: string hashTable * string -> unit;
val delete: string hashTable * string -> unit;
end
= Hash;
```
For the above to make sense, we need to assume that the structure Hash has a type 'a hashTable representing a hash table whose elements are of arbitrary type. If that were not the case, then the type of a hash table would probably be 'a list array.

Solutions for Section 8.6

Exercise 8.6.1

The cycles are:
1. 0000 is a cycle by itself.
2. 1001 is a cycle by itself.
3. 1110 and 0111 form a cycle of length 2.
4. 1100, 0110, and 0011 form a cycle of length 3.
5. 1010, 0101, and 1111 form a cycle of length 3.
6. 1000, 0100, 0010, 0001, 1101, and 1011 form a cycle of length 6.