Elements of ML Programming, 2nd Edition (ML97) |

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;## 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## Solutions for Section 5.3

## Exercise 5.3.1(a)

rev1can 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 typeint 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)

Althoughrev2can 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 ofrev2), 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, namelyint -> chr.## Exercise 5.3.2(a)

For(i), the expression'a~*~'a~*~intis 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~*~intis 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;realis not an equality type, so any type constructed from it will not be an equality type. However, similar types, such asint * (string * string) listare 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. Functionfis 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. Whenfis applied tonil, 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. Variablevmust have a single type, but since both arguments ofhare integers, the typeint listworks forv.## Exercise 5.3.7(g)

Illegal. The type ofnil::vis'a list list. We thus have a variable in the type of an expansive expression.## 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 fors=""is forced, by theorelse, to occur before the test thatsdoes 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 functioninit_a, using the built-in functionsubstringdescribed in Section 9.2.5:fun init_a(s) = (substring(s,0,1) = "a");Notice thatsubstring(s,0,1)extracts from stringsthe 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), applyingFto 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 listL. We then take the first of the resulting suffixes and make a copy of it to which the head ofLis 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);## 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 tomapof Section 5.6.3. The fact that the result ofF(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 applyfis shown in the penultimate line of the code of Exercise 5.5.3. Functionfis 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, functionhereturnstruewhen its argument is any string that contains anhfollowed by aneand returnsfalseotherwise.## 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 functionsheetc. at an intermediate step. We could have appliedfdirectly, byapplyList (f ["he", "she", "her", "his"]) "hershey";## Exercise 5.5.7(a)

fun curry F x1 x2 ... xn= F(x1,x2,...,xn)## 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 strconverts 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,orelseis 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 ofIare functions from integers to strings.## Exercise 5.6.4

(a) Type =(int -> 'a) -> int -> 'a. FunctioncompA1takes as argument a functionF(x)and produces a functionG(x)such thatG(x)=F(x+1). Here,xmust be an integer. Put another way,compA1turns a functionF(x)intoF(x+1).(b) Type =

((int -> 'a) -> 'b) -> (int -> 'a) -> 'b. The functioncompCompA1takes a functionFand turns it intoF o compA1.(c) Type =

int -> int. Functionfis defined byf(x)=x+2. The explanation is thatcompA1turns anyF(x)intoF(x+1), so ifFisadd1,f(x)will beadd1(x+1), orx+2.(d) Type =

int, andf(2)=4.(e) Type =

(int -> 'a) -> int -> 'a. Functiongtakes its argument functionF(x)and produces the functionF(x+2).(f) Type =

int -> int. Functionhtakes integerxand producesx+3.(g) Type =

int, andh(2)=5.