Elements of ML Programming, 2nd Edition (ML97)

## Solutions for Chapter 7

Solutions for Section 7.1

## 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);
```

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).

## 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);
```

### 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;
```

### 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);
```

## 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;
```

## 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
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);
```

## 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)
);
```

### 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.