|Elements of ML Programming, 2nd Edition (ML97)|
Solutions for Section 6.2
Solutions for Section 6.3
Solutions for Section 6.4
type 'a setOfSets = 'a list list;
type ('d, 'r) mapTree = ('d * 'r) btree;Then, we can define the desired tree by
val t1 = Node(("a",1), Empty, Empty): (string, int) mapTree;
open TextIO; datatype intOrEof = Eof | Int of int; fun digit(c) = c >= #"0" andalso c <= #"9"; fun startInt(file) = startInt1(file, input1(file)) and startInt1(file, NONE) = Eof | startInt1(file, SOME c) = if digit(c) then Int(ord(c)-ord(#"0")) else startInt(file); fun finishInt(i,file) = if i = Eof then Eof else finishInt1(i,file,input1(file)) and finishInt1(i, file, NONE) = i | finishInt1(i as Int(j), file, SOME c) = if digit(c) then finishInt(Int(10*j+ord(c)-ord(#"0")), file) else i; fun getInt(file) = finishInt(startInt(file), file) fun sumInts1(file) = let val i = getInt(file) in if i = Eof then 0 else let val Int(j) = i in j + sumInts1(file) end end; fun sumInts(filename) = sumInts1(openIn(filename));Download this program
datatype suit = Club | Heart | Diamond | Spade;
datatype thing = Int of int | Thing of thing listHere is a typical value of the datatype thing.
Thing([Int(1), Thing([Int(2)]), Int(3)]);
type 'node graph = ('node * 'node list) list; exception NotANode; (* succ(a,G) looks up the list of successors of node a in graph G *) fun succ(a,nil) = raise NotANode | succ(a,(b,L)::tail) = if a=b then L else succ(a,tail); (* member(a,L) determines whether a is on list L *) fun member(a,nil) = false | member(a,b::bs) = if a=b then true else member(a,bs); (* search1(L,R,G) finds all the nodes reachable from any of the list of nodes L in graph G, but does not search from the set R of nodes that have already been reached. R is included in the set of reached nodes that is eventually returned. *) fun search1(nil,R,G) = R | search1(x::xs,R,G) = if member(x,R) then search1(xs,R,G) else (* x is a new node, never before seen *) search1(succ(x,G)@xs, x::R, G); (* search(a,G) finds the set of nodes reachable from a in graph G *) fun search(a,G) = search1([a],nil,G);Download this program
Return to Top
fun lookup lt Empty a = raise Missing | lookup lt (Node((c,b),left,right)) a = if lt(a,c) then lookup lt left a else if lt(c,a) then lookup lt right a else (* a=c *) b;
val lookup1 = lookup (op < : real*real->bool);and similarly for the other two functions. An alternative is
val lookup1 = lookup (fn (x:real,y) => x<y);using an anonymous function. However, beware
val lookup1 = lookup (op <:real*real->bool);which, although it looks almost identical to our first solution, is an error. Do you see why?
val lookupS = lookup (op <) ( Node(16, Node(4, Node(1,Empty,Empty), Node(9,Empty,Empty) ), Node(36, Node(25,Empty,Empty), Empty ) ) );Download this program
Return to Top
fun isOn (Node(a,nil)) x = (a=x) | isOn (Node(a,t::ts)) x = isOn t x orelse isOn (Node(a,ts)) x;For part (b), we found it more convenient to put the element x first among the arguments. Then, the following works:
fun isOn x (Node(a,L)) = (a=x) orelse foldr (fn (x,y) => x orelse y) false (map (isOn x) L);If x is required to be the second argument, then we need to define another anonymous function to take the place of isOn x, which is a function that takes a tree as argument and tells whether x is on that tree. Note that in the above code, (map (isOn x) L) returns a list of booleans, each telling whether x is on one of the subtrees in the list L. Then, foldr is applied to the function that takes the OR of its arguments, an initial value false, and the list of booleans that resulted from the application of map.
fun preOrder(Node(a,nil)) = [a] | preOrder(Node(a,t::ts)) = a :: preOrder(t) @ (tl(preOrder(Node(a,ts))));
fun preOrder1(Node(a,nil), L) = a::L | preOrder1(Node(a,t::ts), L) = a :: preOrder1(t, tl(preOrder1(Node(a,ts),L))); fun preOrder(T) = preOrder1(T,nil);Function preOrder1 takes a tree and a list of labels L that must be appended to the preorder of the tree. If the tree is a single node, then the result is the label a of that node followed by the list L. If the root has one or more subtrees, a call to preOrder1 computes the preorder listing of the tree with the first subtree removed, followed by the list L. We use tl to remove the premature occurrence of the root label a from this list. The list then becomes the second argument of another call to preOrder1, which applies to the first subtree and results in the preorder listing of that subtree followed by the preorder listings of all the other subtrees, and then the list L. Since a is put on the front of this list, preOrder1 correctly returns the preorder listing of its tree argument followed by its second (list) argument.
Return to Top