Elements of ML Programming, Second Edition (ML97): Solutions for Chapter 6

Elements of ML Programming, 2nd Edition (ML97)

Solutions for Chapter 6

Solutions for Section 6.1

Solutions for Section 6.2

Solutions for Section 6.3

Solutions for Section 6.4

Solutions for Section 6.1

Exercise 6.1.1(a)

     type 'a setOfSets = 'a list list;

Exercise 6.2.1

Node(1, Node(2,Empty,Empty), Node(3,Empty,Empty)) is one possible answer.

Exercise 6.2.2

Define the type by

     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;

Exercise 6.2.4

     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

Exercise 6.2.5(a)

     datatype suit = Club | Heart | Diamond | Spade;

Exercise 6.2.5(c)

We need a recursive datatype with a basis data constructor, say Int, to wrap integers, and an inductive data constructor, say Thing, to wrap a list of things. An appropriate declaration is

     datatype thing =
         Int of int |
         Thing of thing list

Here is a typical value of the datatype thing.

     Thing([Int(1), Thing([Int(2)]), Int(3)]);

Exercise 6.2.7

     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

Solutions for Section 6.3

Exercise 6.3.2(a)

     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;

Exercise 6.3.3(a)

     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?

Exercise 6.3.4

The idea is to form the set of integers into as balanced a binary tree as we can. The longest paths will then be proportional to the logarithm of the size of S. Here is an example where the set of integers is 1, 4, 9, 16, 25, and 36. We leave as an interesting challenge a function that will take a list of integers and form them into a binary search tree that is as balanced as possible.

     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

Solutions for Section 6.4

Exercise 6.4.1

Here is a solution to part (a). We test whether x is at the root, and if not, test whether it is either in the first subtree or in the tree obtained by removing the first subtree.

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.

Exercise 6.4.4(a)

     fun preOrder(Node(a,nil)) = [a]
     |   preOrder(Node(a,t::ts)) =
              a :: preOrder(t) @ (tl(preOrder(Node(a,ts))));

Exercise 6.4.6

     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