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

Elements of ML Programming, 2nd Edition (ML97)

Solutions for Chapter 3

Solutions for Section 3.1

Solutions for Section 3.2

Solutions for Section 3.3

Solutions for Section 3.4

Solutions for Section 3.5

Solutions for Section 3.6

Solutions for Section 3.1

Revised 3/17/05.

Exercise 3.1.1(a)

     fun cube(x:real) = x*x*x;

Exercise 3.1.1(c)

     fun third(L) = hd(tl(tl(L)));

Exercise 3.1.1(e)

     fun thirdChar(s) = third(explode(s));

Exercise 3.1.2(a)

     fun minMax(a,b,c) =
         if a<b then
             if b<c then (a,c)
             else (* b is largest *)
                 if a<c then (a,b) else (c,b)
         else (* a >= b *)
             if a<c then (b,c)
             else (* a is largest *)
                 if b<c then (b,a) else (c,a);

Exercise 3.1.3(a)

f multiplies its argument by 2, so the result is 8.

Exercise 3.1.3(b)

The value of f(4) is still 8, and the previous definition of b was 3, so the result is 11. Note that the b referred to in the expression f(4)+b cannot be the b that is the parameter of f, because the latter is only accessible within the definition of f.

Exercise 3.1.3(e)

g(6) = 6+3, so we must compute f(9), or 18.

Return to Top

Solutions for Section 3.2

Exercise 3.2.1(a)

     fun fact(n) =
             if n<=1 then 1 else n*fact(n-1);

Exercise 3.2.1(c)

     fun duplicate(L) =
             if L=nil then nil else hd(L)::hd(L)::duplicate(tl(L));

Exercise 3.2.1(f)

Note: Because real is not an equality type, and the function null to test whether a list is empty even if the list is not of an equality type is not introduced in Chapter 3, I have changed Exercise 3.2.1(f) to ask for the maximum of a list of strings instead, and the code below reflects that change. If you want to make the code work for lists of reals, you have to replace tl(L)=nil in the second line by null(tl(L)), and of course change the type declaration on line (1).

fun maxList(L: string list) =
	if tl(L)=nil (* L is a single element *)
		then hd(L) (* the single element is the maximum *)
		else (* assume there are at least 2 elements *)
			if hd(L)>hd(tl(L)) (* the first element
					exceeds the second *)
				then maxList(hd(L)::tl(tl(L))) (* eliminate
						second element *)
				else maxList(tl(L)) (* eliminate first
						element *);

Download this program

There are considerably simpler ways to solve this problem if we use the let-construct described in Section 3.4.

Exercise 3.2.2

In the second line we have expression c+1. Since 1 is an integer, c must also be an integer. In the third line, the expressions following the then and else must be of the same type. One of these is c, so the type of both is integer. Thus, expression b+d is of integer type. Therefore b and d must also be integers. Finally, since a and b are compared on lines 2 and 3, they must be of the same type. Hence a is also an integer.

Exercise 3.2.3(a)

Since a is compared with b+c, the latter sum must be an integer. Therefore both b and c must be integers. We cannot tell what types d and e have, although they must be of the same type.

Exercise 3.2.3(c)

Since a is compared with b, b must be an integer. Therefore, the sum b+c is an integer, and so is c. Also, d+e must have the same type as b+c, so both d and e are integers as well.

Exercise 3.2.2(f)

Since there is no way to infer a type for b or c without using the default rules, the default applies to operator <. Thus, b and c are both inferred to be integers. We still cannot infer types for d or e. However, since they are each the result in one branch of the if-then-else, their types must be the same.

Return to Top

Solutions for Section 3.3

Exercise 3.3.1(a)

     fun fact(1) = 1
     |   fact(n) = n*fact(n-1);

Exercise 3.3.1(d)

     fun duplicate(nil) = nil
     |   duplicate(x::xs) = x::x::duplicate(xs);

Exercise 3.3.1(f)

     fun maxList([x:real]) = x
     |   maxList(x::y::zs) =
             if x<y then maxList(y::zs)
             else maxList(x::zs);

Exercise 3.3.5(a)

Yes; x="a", y="b", zs=["c"], and w=["d","e"].

Exercise 3.3.5(c)

No; the expression y::zs in the pattern is forced to match nil in the expression. We fail, since constant symbols :: and nil cannot be matched. Put another way, the first component of the pair has to be a list of length at least 2 in order to match the pattern x::y::zs.

Exercise 3.3.7

     fun square(0) = 0
     |   square(n) = square(n-1)+2*n-1;

Exercise 3.3.8

     fun flip(nil) = nil
     |   flip((x as (a:int,b))::xs) =
             if a<b then x::flip(xs) else (b,a)::flip(xs);

Exercise 3.3.11(a)

We first check to see whether the set S is empty, that is, whether the list is nil. If so, x is not in S. If not, then we compare x with the head of the list. If the head equals x, then x is in S. Otherwise, we recursively test whether x is in the tail of the list.

     fun member(_,nil) = false
     |   member(x,y::ys) =
             (x=y orelse member(x,ys));

We might be tempted to replace the second line by

     |   member(x,x::xs) = true
     |   member(x,_::xs) = member(x,xs);

However, it is not permitted to use an identifier like x twice in one pattern.

Exercise 3.3.11(c)

     fun insert(x,nil) = [x]
     |   insert(x,S as y::ys) =
             if x=y then S else y::insert(x,ys);

Exercise 3.3.12

     fun insertAll(a,nil) = nil
     |   insertAll(a,L::Ls) = (a::L)::insertAll(a,Ls);

The idea behind the second line is that we put a on the front of the first list, and then in the recursive call put a on the front of the remaining lists.

Exercise 3.3.13

     fun powerSet(nil) = [nil]
     |   powerSet(x::xs) =
             powerSet(xs)@insertAll(x,powerSet(xs));

The function above computes the power set as follows. For a basis, the power set of the empty set is the set containing the empty set. The latter is represented by the list [nil], as in the first line of function powerSet above. If the given list is not empty, we take the first element x, compute the power set of the remaining elements, and concatenate this list with the list of all sets with x added. Thus, all the sets that have x and those that do not are included in the overall list. Incidentally, there is a better way to write this function that does not require us to compute powerSet(xs) twice. However, we do not discuss the needed construct, the ``let''-expression, until Section 3.4.

Exercise 3.3.14

     fun prodDiff1(_,nil) = 1.0
     |   prodDiff1(a,b::bs) = (a-b)*prodDiff1(a,bs);

     fun prodDiff(nil) = 1.0
     |   prodDiff(b::bs) = prodDiff1(b,bs)*prodDiff(bs);

Exercise 3.3.15

     fun emptyList(nil) = true
     |   emptyList(_) = false;

Return to Top

Solutions for Section 3.4

Exercise 3.4.1

The function below is about as succinct as can be managed.

     fun thousandthPower(x:real) =
             let
                 val x = x*x*x*x*x;
                 val x = x*x*x*x*x;
                 val x = x*x*x*x*x
             in
                 x*x*x*x*x*x*x*x
             end;

Download this program

Exercise 3.4.3

The following code uses insertAll from Exercise 3.3.12.

     fun powerSet(nil) = [nil]
     |   powerSet(x::xs) =
             let
                 val L = powerSet(xs)
             in
                 L @ insertAll(x,L)
             end;

Download the complete program

Exercise 3.4.5

     fun doubleExp(x:real,0) = x
     |   doubleExp(x,i) =
             let
                 val y = doubleExp(x,i-1)
             in
                 y*y
             end;

Note that we could have written the recursive case simply as

     |   doubleExp(x,i) = doubleExp(x,i-1) * doubleExp(x,i-1);

However, it would take considerably more time to compute the function this way, as computations would then be repeated an exponential number of times.

Return to Top

Solutions for Section 3.5

Exercise 3.5.1

     fun cat(nil,M) = M
     |   cat(x::xs,M) = x::cat(xs,M);

That is, we recursively put the tail of L in front of M, and finally put the head of L in front of all, using the cons operator.

Return to Top

Solutions for Section 3.6

Exercise 3.6.4

If the list of roots is empty, the polynomial 1, represented by the list [1.0], is appropriate. If the list is not empty, then let p be the first root. We may recursively construct the polynomial for the rest of the roots and multiply it by x-p, or in list representation [~p,1.0]. The following lines implement this idea.

     fun polyFromRoots(nil) = [1.0]
     |   polyFromRoots(p::ps) =
             pmult([~p,1.0],polyFromRoots(ps));

Return to Top