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

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

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

structure BinaryTree: BTREE = struct structure Element = Pair; type elt = int * int; (* suitable definitions for btree and the functions *) end;However, should we replace

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;

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

- 0000 is a cycle by itself.
- 1001 is a cycle by itself.
- 1110 and 0111 form a cycle of length 2.
- 1100, 0110, and 0011 form a cycle of length 3.
- 1010, 0101, and 1111 form a cycle of length 3.
- 1000, 0100, 0010, 0001, 1101, and 1011 form a cycle of length 6.