| Elements of ML Programming, 2nd Edition (ML97) |
|
| 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)
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.
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);
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)
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.