Elements of ML Programming, 2nd Edition (ML97)

Solutions for Chapter 7

Solutions for Section 7.1

Solutions for Section 7.2

Solutions for Section 7.3

Solutions for Section 7.4

Solutions for Section 7.5

Solutions for Section 7.1

Exercise 7.1.1(a)

     type dino = {name:string, height:real, weight:real};

Exercise 7.1.1(c)

     val brachio:dino =
         {name="Brachiosaurus", height=40.0, weight=50.0}

Exercise 7.1.1(e)

     #weight(brachio)

Exercise 7.1.2(a)

     fun tallest (L : dino list) = foldr Real.max 0.0 (map (#height) L);
We must declare L to be a dino list, so ML can deduce the type of records in the list. We then use map to apply to each record on the list L the function #height that extracts the height component. The resulting list of reals is folded, using the function Real.max in the structure Real that takes the maximum of two reals.

Exercise 7.1.3(a)

     type student = {name:string, ID:int, courses: string list};

     (* findName(n,L) produces those student records with
        name field n *)
     fun findName(n,nil) = nil
     |   findName(n,(r:student)::rs) =
             if n = #name(r) then r::findName(n,rs)
             else findName(n,rs);
A simpler version of findName uses a built-in function List.filter that is a Curried version of the function filter that we discussed in Section 5.4.5. To get the built-in filter, we must go to another of the structures, List, that is found in the standard basis; see Section 9.4.7. Here is the code:
     fun findName(n,L) =
             List.filter (fn (r:student) => (n = #name(r))) L;
That is, we filter the list of student records L using the predicate that the name field of the record be n.

Exercise 7.1.3(c)

     (* enrollment(c,L) produces the names in those of the
        records on list L that have a course list including
        course c *)
     fun enrollment(c,nil) = nil
     |   enrollment(c,(r:student)::rs) =
             if #courses(r) = nil then enrollment(c,rs)
             else if c = hd(#courses(r)) then
                 #name(r)::enrollment(c,rs)
             else enrollment(c, {name = #name(r), ID = #ID(r),
                     courses = tl(#courses(r))}::rs);
Download this program and the code for Exercise 7.1.3(a)

This function uses a trick that first appeared in Section 6.4.2, where we operated upon a tree by modifying the tree to remove one node at a time. Here, we could have written a function that tests whether a given course is present in a list of courses, and used that in the function enrollment. Instead, we have chosen to write only one function, which, when it does not find the desired course c at the head of the list of courses, calls itself recursively with the head of the course list removed. The first two cases of this function handle the situations where the list of courses is empty (when c is surely not among them), and where the head of the list equals c (when c surely is among the courses).

Return to Top

Solutions for Section 7.2

Exercise 7.2.1(a)

     val A = Array.array(20, nil : real list);

Exercise 7.2.1(c)

     Array.sub(A,29);

Exercise 7.2.1(e)

     Array.update(A, 10, 43);

Exercise 7.2.2(a)

     open Array;

     (* swap exchanges A[i] with A[j] *)
     fun swap(A,i,j) =
             let
                 val temp = sub(A,i)
             in
                 (update(A,i,sub(A,j)); update(A,j,temp))
             end;

     (* insert(A,i) pushes A[i] left until it finds an array element
        smaller than it.  i.e., insert(A,i) inserts A[i] into its
        proper place in a sorted array A[0]...A[i-1] *)
     fun insert(A,0) = ()
     |   insert(A,i) =
             if sub(A,i-1) >= sub(A,i) then
                 (swap(A,i-1,i); insert(A,i-1))
             else ();

     (* isort1(A,i,n) inserts A[i]...A[n-1] into the sorted array
        A[0]...A[i-1] *)
     fun isort1(A,i,n) =
             if i>=n then ()
             else (insert(A,i); isort1(A,i+1,n));

     (* An insertion-sort function *)
     fun isort(A,n) = isort1(A,1,n);
Download this program

Exercise 7.2.3(a)

     (* cycle1 moves positions i,...,n-1 of array A one position down *)
     fun cycle1(A,n,i) =
             if i >= n then ()
             else (
                     Array.update(A,i-1,Array.sub(A,i));
                     cycle1(A,n,i+1)
             );
     
     fun cycle(A,n) =
             let
                 val temp = Array.sub(A,0)
             in
                 (
                     cycle1(A,n,1);
                     Array.update(A,n-1,temp)
                 )
             end;
Download this program

Exercise 7.2.3(c)

     (* rev1 reverses A[i] through A[n-i-1] *)
     fun rev1(A,n,i) =
             if 2*i+1 >= n then ()
             else
                 let
                     val temp = Array.sub(A,i);
                 in
                     (
                         Array.update(A,i,Array.sub(A,n-i-1));
                         Array.update(A,n-i-1,temp);
                         rev1(A,n,i+1)
                     )
                 end;
     
     fun reverse(A,n) = rev1(A,n,0);
Download this program

Return to Top

Solutions for Section 7.3

Exercise 7.3.1(a)

     val i = ref 10;

Exercise 7.3.1(c)

     i := 20;

Exercise 7.3.2(a)

     (!x+!y)*(!x+!y);

Exercise 7.3.3

An expression must follow the do, and a val-declaration is not an expression. You get a syntax error message.

Exercise 7.3.5(a)

     datatype 'a linkedList = Nil |
         Cell of {element: 'a, next: 'a linkedList ref};
For instance, a cell with element 1 and a nil next pointer could be defined by
     val c1 = Cell{element=1, next= ref Nil};
Notice that no parentheses are needed around the argument of a Cell data constructor, because the curly braces group its argument properly.

Exercise 7.3.5(c)

     fun skip Nil = raise BadCell
     |   skip(Cell{next = ref Nil,...}) = raise BadCell
     |   skip(Cell{next = x as ref(Cell{next=y,...}),...}) =
             x := !y;
Download code for Exercise 7.3.5(a,c)

Return to Top

Solutions for Section 7.4

Exercise 7.4.1

     datatype 'a bucket = Empty | Deleted | Filled of 'a;

     (* search for x starting at bucket i, but not passing bucket j.
        Here and elsewhere, n is the number of buckets. *)
     fun lookup1(A,i,j,n,x) =
             if Array.sub(A,i) = Filled(x) then true
             else if Array.sub(A,i) = Empty then false
             else if i=j then false (* we have searched the whole
                                       hash table *)
             else lookup1(A,(i+1) mod n,j,n,x);

     (* lookup x in hash table A of n buckets, using hash function h *)
     fun lookup(A,h,n,x) = lookup1(A,h(x),(h(x)-1) mod n,n,x);

     (* delete1 deletes x from A; parameters are as for lookup1 *)
     fun delete1(A,i,j,n,x) =
             if Array.sub(A,i) = Filled(x) then
                 Array.update(A,i,Deleted)
             else if Array.sub(A,i) = Empty then () (* x cannot be
                             in the hash table *)
             else if i=j then () (* we have searched all buckets and
                             not found x *)
             else delete1(A,(i+1) mod n,j,n,x);

     (* delete takes parameters like lookup *)
     fun delete(A,h,n,x) = delete1(A,h(x),(h(x)-1) mod n,n,x);

     exception NoMoreRoom;

     (* insert1 is analogous to lookup1 *)
     fun insert1(A,i,j,n,x) =
             if Array.sub(A,i) = Empty orelse Array.sub(A,i) = Deleted then
                     Array.update(A,i,Filled(x))
             else if i=j then raise NoMoreRoom
             else insert1(A,(i+1) mod n,j,n,x);

     (* insert is analogous to lookup *)
     fun insert(A,h,n,x) = insert1(A,h(x),(h(x)-1) mod n,n,x);
Download this program

Return to Top

Solutions for Section 7.5

Exercise 7.5.1

     open Array;

     fun pivot(M,m,n) =
             if m>=n then 0.0
             else if m=n-1 then sub(sub(M,m),m)
             else (* 0<m<n-1 *) (
                 let (* normalize  row m to right of diagonal *)
                     val i = ref (m+1);
                     val a = sub(sub(M,m),m)
                 in
                     while !i<n do (
                         update(sub(M,m), !i, sub(sub(M,m),!i)/a);
                         i := !i + 1
                     )
                 end;
                 let (* subtract M[i,m]*M[m,j] from M[i,j]
                        for all i and j such that m<i,j<n *)
                     val i = ref (m+1);
                     val j = ref (m+1)
                 in
                     while !i<n do (
                         while !j<n do (
                             update(sub(M,!i),!j,sub(sub(M,!i),!j)-
                                 sub(sub(M,!i),m)*sub(sub(M,m),!j));
                             j := !j + 1
                         );
                         j := m + 1;
                         i := !i + 1
                     )
                 end;
                 (* result is M[m,m] times recursive call on matrix
                    starting at row and column m+1 *)
                 sub(sub(M,m),m)*pivot(M,m+1,n)
             );
Download this program

Exercise 7.5.2

The functions condense of Exercise 5.2.4 and pivot of Exercise 7.5.1 each take time proportional to n^3 on a matrix of side n. Observe that in Exercise 5.2.4, functions normalize and condense1 each take time proportional to n. Function condense2 calls condense1 no more than n times and thus takes time proportional to n^2. Finally, condense calls normalize and condense2 no more than n times each, and thus takes time proportional to n^3. Function pivot of Exercise 7.5.1 uses two nested loops, each of which repeats no more than n times. Function pivot thus takes time proportional to n^2 before calling itself recursively with the next higher value of m. Since m ranges from 0 to n-1, there are n recursive calls. Each takes time proportional to n^2, so the total time is proportional to n^3.

Exercise 7.5.4(a)

     fun matrix(n,m,v:real) =
         let
             val M = Array.array(n,Array.array(m,v));
             val i = ref 1
         in
             (
                 while !i<n do (
                     Array.update(M,!i,Array.array(m,v));
                     i := !i + 1
                 );
                 M
             )
         end;

A matrix is an array of arrays.
Notice that when we initialize a matrix we have to create a new array
for each row of the matrix, which we do in the while-loop.

Download this program

Exercise 7.5.6(a)

     for(1,10,fn x=>(print(Int.toString x); print " "));