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

Elements of ML Programming, 2nd Edition (ML97)

Solutions for Chapter 9

Solutions for Section 9.1

Solutions for Section 9.2

Solutions for Section 9.3

Solutions for Section 9.4

Solutions for Section 9.5

Solutions for Section 9.1

Exercise 9.1.1(a)

Yes. Leaves 2 and 3 would be grouped first, and the tree printed would be (1,(2,3)).

Exercise 9.1.2(a)

Give both the same precedence and make them left-associative. For example,

     infix 6 +;
     infix 6 *;

Exercise 9.1.3

We need to keep the precedences of the polynomial operators below 6, which is the precedence of the additive arithmetic operators. Thus, we could use something like

     infix 2 padd;
     infix 3 pmult;
     infix 4 smult;

Here is an answer to part (b), where we compute (P+2Q)*R.

([~6.0,0.0,5.0,0.0,3.0] padd 2.0 smult [4.0,~3.0,2.0,1.0]) pmult [1.0,1.0]

Exercise 9.1.5(a)

     fun sumLeaves(x:real) = x
     |   sumLeaves(T1 t T2) = sumLeaves(T1) + sumLeaves(T2);

Return to Top

Solutions for Section 9.2

Exercise 9.2.1

     (x + abs(x))/2.0;

When x is positive, the above expression is just 2x/2 = x. However, when x is negative, the numerator is 0.

Exercise 9.2.2

It's not possible. The problem is that the given expresion is not continuous; it jumps from 0 to over 3 as x moves from 3 to 3+epsilon. However, all the given functions, abs and the arithmetic operators, are continuous, and therefore so will be any expression made from them, except at points where the constructed expression is undefined or infinite (of which the given expression has none, so the constructed expression could not have).

Exercise 9.2.3(a)

"23".

Exercise 9.2.3(d)

"abc".

Exercise 9.2.3(e)

"abc".

Exercise 9.2.6(a)

     fun addToRef(r,x) = ignore(r := !r + x);

Exercise 9.2.8(a)

     fun isSome(NONE) = false
     |   isSome(SOME x) = true;

Exercise 9.2.8(c)

     fun getOpt(NONE,x) = x
     |   getOpt(SOME y, _) = y;

Exercise 9.2.8(e)

     fun ignore x = (x; ());

Exercise 9.2.8(g)

     fun app f L = ignore(map f L);

Notice the difference:

app print ["ab", "cd"];
abcdval it = () : unit
map print ["ab", "cd"];
abcdval it = [(),()] : unit list

Return to Top

Solutions for Section 9.3

Exercise 9.3.1

     fun compare(nil,nil) = EQUAL
     |   compare(nil,_) = LESS
     |   compare(_,nil) = GREATER
     |   compare(x::xs,y::ys) =
             if x<y then LESS
             else if x>y then GREATER
             else compare(xs,ys);

Notice that the function compare works only on integer lists, because integer is the default type for <.

Download this program

Return to Top

Solutions for Section 9.4

Exercise 9.4.1(a,b)

The quotient is 2 and the remainder is -4. However, there is an error in the text because in SML/NJ version 109.30, quot and rem are prefix operators, i.e., functions. Thus, the correct expressions are quot(~14,~5) and rem(~14,~5). The same applies to parts (c) and (d) of this exercise.

Exercise 9.4.2(a)

     x * sign(x)

When x is positive, sign(x) is 1, so the result is x. When x is negative, sign(x) is -1, so the result is -x, i.e., abs(x). When x is 0, then sign(x) is also 0, and the expression is surely 0.

Exercise 9.4.3(a)

2748.

Exercise 9.4.3(c)

~1073741821

Exercise 9.4.3(e)

0wx1F

Exercise 9.4.3(g)

0wx4

Exercise 9.4.6(a)

     fun isVowel c = Char.contains "aeiou" c;

Exercise 9.4.7(a)

In the following, we assume the only whitespace characters are blank, tab, and newline.

     val f = String.tokens(fn x => x = #" " orelse x = #"\n" orelse x = #"\t");

Exercise 9.4.8

     fun rev1 ss =
         case Substring.getc ss of
             NONE => "" |
             SOME (c,ss1) => rev1 ss1 ^ str c;

     fun revString s = rev1(Substring.substring(s,0,size s));

The work is done by the function rev1, which uses getc to break a substring into a first character and a subsequent characters. If the substring is empty, we return the empty string (not substring). If the string has a first character, we recursively reverse the substring consisting of the remaining characters, receiving a string as the result. Finally, we concatenate the first character to the end of the result string.

Then, since we are given a string initially, we need function revString to convert the string to an equivalent substring and call rev1 on this substring. Notice that we get the complete string as a substring by taking the second argument of Substring.substring to be 0 and the third argument to be the length of the string.

Download this program

Exercise 9.4.9(a)

[0,1,4,9]

Exercise 9.4.9(c)

Exercise 9.4.10(b)

     fun threeWay(L) =
             let
                  val (L0,M) = List.partition (fn x => x mod 3 = 0) L;
                  val (L1,L2) = List.partition (fn x => x mod 3 = 1) M
             in
                  (L0,L1,L2)
             end;

Here, L0, L1, and L2 are the lists of integers that have remainders 0, 1, and 2, respectively, when divided by 3. Download this program

Exercise 9.4.11(a)

     fun chArray() = Array.tabulate(26, (fn x => chr(x+ord #"a")));

Exercise 9.4.12(a)

     #[1,4,9,16,25]

Exercise 9.4.14(a)

     TIME {sec=1, usec=234000}

Exercise 9.4.14(c)

3.002.

Return to Top

Solutions for Section 9.5

Exercise 9.5.2

The following function takes a list of strings, converts them to integers, and sums those integers.

     fun sum1 nil = 0
     |   sum1(x::xs) = valOf(Int.fromString x) + sum1 x;

Then, the following function calls sum1 on its second argument, ignoring the first, and prints the result.

     fun sum(_,L) = print(Int.toString(sum1 L));

The first argument is there because of the form of function exportFn expects; it is the name of the file containing the program being exported.

Finally, we export the function sum into a file foo:

     exportFn("foo",sum);

Return to Top