Elements of ML Programming, 2nd Edition (ML97)

Solutions for Chapter 5

Solutions for Section 5.1

Solutions for Section 5.2

Solutions for Section 5.3

Solutions for Section 5.4

Solutions for Section 5.5

Solutions for Section 5.6

Solutions for Section 5.1

Exercise 5.1.2(a)

     val rec padd = fn
             (P,nil) => P |
             (nil,Q) => Q |
             ((p:real)::ps, q::qs) => (p+q)::padd(ps, qs);

Exercise 5.1.2(e)

     val rec printList = fn
             nil => () |
             x::xs => (
                 print(Int.toString(x));
                 print("\n"); 
                 printList(xs)
             );

Exercise 5.1.3

The most useful case-expression is probably the following.
     case y mod 400 of
         0 => true |
         100 => false |
         200 => false |
         300 => false |
         _ => y mod 4 = 0;

Exercise 5.1.4(a)

     case E of
         true => true |
         false => F;

Return to Top

Solutions for Section 5.2

Exercise 5.2.2

Modified 6/11/04.

     exception Negative of int;

     fun fact1(0) = 1
     |   fact1(n) =
             if n>0 then n*fact1(n-1)
             else raise Negative(n);

     fun fact(n) = fact1(n) handle Negative(n) => (
         print("Warning: negative argument ");
         print(Int.toString(n));
         print(" found\n");
         0
     );

Exercise 5.2.3

     open TextIO;

     exception Eof;

     fun digit(c) = c >= #"0" andalso c <= #"9";

     fun startInt(file) = startInt1(file, input1(file))

     and startInt1(file, NONE) = raise Eof
     |   startInt1(file, SOME c) =
             if digit(c) then ord(c)-ord(#"0")
             else startInt(file);

     fun finishInt(i,file) =
             finishInt1(i,file,input1(file))

     and finishInt1(i, file, NONE) = i
     |   finishInt1(i, file, SOME c) =
             if digit(c) then
                     finishInt(10*i+ord(c)-ord(#"0"), file)
             else i;

     fun getInt(file) = finishInt(startInt(file), file)

     fun sumInts1(file) =
             (getInt(file) + sumInts1(file)) handle Eof => 0;

     fun sumInts(filename) = sumInts1(openIn(filename));
Download this program

Exercise 5.2.4

exception Unnormalizable;

exception Misshaped;

(* normalize(a,L) divides each element of list L by a *)
fun normalize(a,nil) = nil
|   normalize(a,r::rs) = r/a::normalize(a,rs);

(* condense1(b,L1,L2) subtracts from the jth element of L2
	b times the jth element of L1 for all j and produces
	the resulting L2 *)
fun condense1(b:real,nil,nil) = nil
|   condense1(b,x::xs,y::ys) = (y-b*x)::condense1(b,xs,ys)
|   condense1(_) = raise Misshaped; (* one list is longer
			than the other *)

(* condense2(L,M) takes a list L and a list of lists M, and
	considers each list L' on M.  For L', we subtract from
	each element in the tail of L' the product of the head
	of L' and the corresponding element of list L *)
fun condense2(L,nil) = nil
|   condense2(L,(x::xs)::Rs) =
			condense1(x,L,xs)::condense2(L,Rs);

(* condense(M) applies pivotal condensation to matrix M *)
fun condense([[a]]) = a
|   condense((b::bs)::Rs) =
        if b <= 0.0 andalso b >= 0.0 then raise Unnormalizable
		(* above tests if b=0.0; recall that testing
		   equality with a real is illegal, as is using
		   a real in a pattern.  If b=0.0, then we cannot
		   normalize, because a division by 0.0 is called
		   for *)
        else
	    let
		val L = normalize(b,bs);
		val M' = condense2(L,Rs)
	    in
		b*condense(M')
	    end
|   condense(_) = raise Misshaped; (* the number of rows
			does not equal the length of each row *)
Download this program

Exercise 5.2.5(a)

string -> exn

Return to Top

Solutions for Section 5.3

Exercise 5.3.1(a)

rev1 can only take lists of equality types as arguments. Thus, even if we specify the type of list elements, as we have done here by mentioning the type int list -> int list, it is an error, since the specified type is a function type and therefore not an equality type.

Exercise 5.3.1(d)

Although rev2 can take as argument lists of any type, including nonequality types such as function types, ML will not evaluate an expression whose type has variables in it. Since the result of this expression is a list of elements of type 'a list -> 'a list (the type of rev2), and this type has the variable 'a, there is an error, and ML tells us there is a ``nongeneralizable type variable'' in the result.

Exercise 5.3.1(f)

This expression is legal. Its result is the list [chr,chr], whose type is concrete, namely int -> chr.

Exercise 5.3.2(a)

For (i), the expression 'a~*~'a~*~int is the only example. For (ii) there are many examples, such as 'a~*~real~list~*~int. For (iii) there are again numerous examples, of which ('c~*~'d~list)~*~'b~*~int is one.

Exercise 5.3.3(a)

     fun f(x,y,z) = (z(x)=y);

Exercise 5.3.3(c)

     fun f(nil, _, z) = z
     |   f(x::xs, _, _) = x;

Exercise 5.3.4(a)

Yes; it is constructed from basic equality types using the list and product-type mechanisms for constructing new equality types.

Exercise 5.3.4(c)

No; the values of this type are functions. Incidently, note the domain type for these functions is integer and the range type is functions that take a character argument and produce the unit as value.

Exercise 5.3.4(d)

No; real is not an equality type, so any type constructed from it will not be an equality type. However, similar types, such as int * (string * string) list are equality types.

Exercise 5.3.5(a)

True. Both sides have the value [(1,2),~(3,4)].

Exercise 5.3.5(c)

True. Both sides have the same value as in Exercise5.3.5(a).

Exercise 5.3.6

Since the ML compiler is able to do compile-time type checking, it never allows to run any code where there is a possible type mismatch, such as between a head and tail of a constructed list.

Exercise 5.3.7(a)

The expression is legal. Function f is of type 'a list -> 'a list. It can be applied to a list of any type; here integer and string lists.

Exercise 5.3.7(b)

Illegal. When f is applied to nil, we cannot determine the type of the result, so the expression's type has a type variable. Since the expression is expansive, and the type variable is nongeneralizable, there is an error.

Exercise 5.3.7(e)

Legal. Variable v must have a single type, but since both arguments of h are integers, the type int list works for v.

Exercise 5.3.7(g)

Illegal. The type of nil::v is 'a list list. We thus have a variable in the type of an expansive expression.

Return to Top

Solutions for Section 5.4

Exercise 5.4.1

(* print a table with rows
	x+i*delta, F(x+i*delta)
for i = 0, 1,...,n-1 *)
fun tabulate(x,delta,0,F) = ()
|   tabulate(x,delta,n,F) = (
	print(Real.toString(x));
	print("\t");
	print(Real.toString(F(x)));
	print("\n");
	tabulate(x+delta,delta,n-1,F)
);
Download this program

Exercise 5.4.3(a)

fun trap(a,b,n,F) = 
	if n<=0 orelse b-a<=0.0 then 0.0
	else
		let
			val delta = (b-a)/real(n);
			fun trap1(x,0) = 0.0
			|   trap1(x,i) = delta*(F(x)+F(x+delta))/2.0
					 + trap1(x+delta,i-1)
		in
			trap1(a,n)
		end;
Download this program

Exercise 5.4.5(a)

     simpleMap(fn(x)=>if x<0.0 then 0.0 else x, L);

Exercise 5.4.5(c)

     simpleMap(fn(c)=>if c>=#"a" andalso c<=#"z" then chr(ord(c)-32)
                      else c,
               L);

Exercise 5.4.6(a)

     reduce(fn(x,y)=> if x<y then y else x, L);

Exercise 5.4.6(c)

     reduce(op ^, L);

Exercise 5.4.7(a)

     filter(fn(x)=>x>0.0, L);

Exercise 5.4.7(c)

Here is a way to write a suitable anonymous function to do the job. Note the importance that the test for s="" is forced, by the orelse, to occur before the test that s does not begin with #"a". If we could not rely on the order of the tests, we might accidently try to find the head of an empty list.
     filter(fn(s)=>not(s="" orelse hd(explode(s)) <> #"a"), L);
Of course, one could define the desired test by a function with two patterns, such as:
     fun init_a("") = false
     |   init_a(s) = (hd(explode(s))=#"a");
There is another, simpler way to write the function init_a, using the built-in function substring described in Section 9.2.5:
     fun init_a(s) = (substring(s,0,1) = "a");
Notice that substring(s,0,1) extracts from string s the substring of length 1 beginning at position 0 (the initial position of the string).

Exercise 5.4.9

The following code works by looking for the first two elements of the list (if they exist), applying F to them to form one element, and recursively reducing the list with the first two elements replaced by one.
     exception EmptyList;

     fun lreduce(F,nil) = raise EmptyList
     |   lreduce(F,[x]) = x
     |   lreduce(F,x::y::zs) = lreduce(F, F(x,y)::zs);

Exercise 5.4.11

     fun reduceB(g,F,nil) = g
     |   reduceB(g,F,x::xs) = F(x, reduceB(g,F,xs));

Exercise 5.4.12(a)

     reduceB(0,fn(x,y)=>y+1, L);

Exercise 5.4.12(b)

     reduceB([nil],fn(x,y)=>(x::hd(y))::y, L);
That is, we compute the suffixes of the tail of a list L. We then take the first of the resulting suffixes and make a copy of it to which the head of L is prepended. This new suffix is the longest possible suffix and is prepended to the list of suffixes of the tail.

Exercise 5.4.13(a)

     fun eval(plus,times,[c],x) = c
     |   eval(plus,times,c::cs,x) =
             plus(c,times(x,eval(plus,times,cs,x)));

Exercise 5.4.13(b)

     eval(fn(x,y)=>x+y, fn(x,y)=>x*y, [1,2,3,4], 5);

Return to Top

Solutions for Section 5.5

Exercise 5.5.1

     fun applyList nil _ = nil
     |   applyList (F::Fs) a = F(a)::(applyList Fs a);

Exercise 5.5.2

     fun makeFnList F nil = nil
     |   makeFnList F (x::xs) = F(x)::(makeFnList F xs);
Notice that this function is equivalent to map of Section 5.6.3. The fact that the result of F(x) is presumed to be a function is irrelevant.

Exercise 5.5.3

     (* ss1(L,M) tests whether list L is a prefix of list M *)
     fun ss1(nil, _) = true
     |   ss1(_, nil) = false
     |   ss1(x::xs, y::ys) = (x=y andalso ss1(xs,ys));

     (* ss2(L,M) tests whether list L is a sublist of list M *)
     fun ss2(x, nil) = ss1(x,nil)
     |   ss2(x, y::ys) = ss1(x,y::ys) orelse ss2(x,ys);

     (* substring converts strings to lists and applies ss2 *)
     fun substring x y = ss2(explode(x),explode(y));

     val f = makeFnList(substring);

     val [he, she, her, his] = f ["he", "she", "her", "his"];

     applyList [he, she, her, his] "hershey";
Download this program

Exercise 5.5.4

The proper way to apply f is shown in the penultimate line of the code of Exercise 5.5.3. Function f is applied to a list of the four strings mentioned in Exercise 5.5.4. The result is a list of four functions; we have given these functions names equal to the strings that they search for. For instance, function he returns true when its argument is any string that contains an h followed by an e and returns false otherwise.

Exercise 5.5.5

The solution to this exercise is in the last line of the code for Exercise 5.5.3. The result is the list [true, true, true, false] since only "his" is not a substring of "hershey". Note that it was not necessary to define the four functions he etc. at an intermediate step. We could have applied f directly, by
     applyList (f ["he", "she", "her", "his"]) "hershey";

Exercise 5.5.7(a)

fun curry F x1 x2 ... xn = F(x1,x2,...,xn)

Return to Top

Solutions for Section 5.6

Exercise 5.6.1(a)

     val f = map real;

Exercise 5.6.1(c)

val f = (foldr (op ^) "") o (map str);
Our solution is the composition of two functions. The first, map str converts a list of characters to a list of strings of length 1. The second, foldr (op ^) "" concatenates the list of strings produced by the first function.

Exercise 5.6.1(e)

     val f = foldr (op -) 0;

Exercise 5.6.1(g)

     val f = foldr (fn (x,y) => x orelse y) false;
One might suspect that the following would work:
     val f = foldr (op orelse) false;
However, orelse is a shorthand for an if-then-else expression, and not a symbol that can be converted into a prefix operator. Thus, we had to define the desired (anonymous) function explicitly.

Exercise 5.6.2

Revised 3/9/02.

     fun foldl F y nil = y
     |   foldl F y (x::xs) = foldl F (F(x,y)) xs;
Notice how the recursive step combines the start value with the first element of the list to create a new start element, which is used to fold the tail of the list.

Exercise 5.6.3(a)

(int -> string) -> int -> string. That is, both the domain and range types of I are functions from integers to strings.

Exercise 5.6.4

(a) Type = (int -> 'a) -> int -> 'a. Function compA1 takes as argument a function F(x) and produces a function G(x) such that G(x)=F(x+1). Here, x must be an integer. Put another way, compA1 turns a function F(x) into F(x+1).

(b) Type = ((int -> 'a) -> 'b) -> (int -> 'a) -> 'b. The function compCompA1 takes a function F and turns it into F o compA1.

(c) Type = int -> int. Function f is defined by f(x)=x+2. The explanation is that compA1 turns any F(x) into F(x+1), so if F is add1, f(x) will be add1(x+1), or x+2.

(d) Type = int, and f(2)=4.

(e) Type = (int -> 'a) -> int -> 'a. Function g takes its argument function F(x) and produces the function F(x+2).

(f) Type = int -> int. Function h takes integer x and produces x+3.

(g) Type = int, and h(2)=5.

Return to Top