| Elements of ML Programming, 2nd Edition (ML97) |
|
| Elements of ML Programming, 2nd Edition (ML97) |
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;
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;
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);
Download code for Exercises 8.2.1, 8.2.2, and
8.2.3.
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
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 xhead::xtail = explode(x);
val yhead::ytail = explode(y);
val xs = implode(xtail);
val ys = implode(ytail)
in
if xhead=yhead then sim(xs,ys)
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.
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.
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;
Download this program
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.