| Elements of ML Programming, 2nd Edition (ML97) |
|
| Elements of ML Programming, 2nd Edition (ML97) |
type dino = {name:string, height:real, weight:real};
val brachio:dino =
{name="Brachiosaurus", height=40.0, weight=50.0}
#weight(brachio)
fun tallest (L : dino list) = foldr Real.max 0.0 (map (#height) L);
We must declare L to be a dino list, so ML can deduce
the type of records in the list.
We then use map to apply to each record on the list L
the function #height that extracts the height component.
The resulting list of reals is folded, using the function
Real.max in the structure Real that takes the maximum
of two reals.
type student = {name:string, ID:int, courses: string list};
(* findName(n,L) produces those student records with
name field n *)
fun findName(n,nil) = nil
| findName(n,(r:student)::rs) =
if n = #name(r) then r::findName(n,rs)
else findName(n,rs);
A simpler version of findName uses a built-in function
List.filter that is a Curried version of the function
filter that we discussed in Section 5.4.5.
To get the built-in filter, we must go to another of the
structures, List, that is found in the standard basis; see
Section 9.4.7.
Here is the code:
fun findName(n,L) =
List.filter (fn (r:student) => (n = #name(r))) L;
That is, we filter the list of student
records L using the predicate that the
name field of the record be n.
(* enrollment(c,L) produces the names in those of the
records on list L that have a course list including
course c *)
fun enrollment(c,nil) = nil
| enrollment(c,(r:student)::rs) =
if #courses(r) = nil then enrollment(c,rs)
else if c = hd(#courses(r)) then
#name(r)::enrollment(c,rs)
else enrollment(c, {name = #name(r), ID = #ID(r),
courses = tl(#courses(r))}::rs);
Download this program and the code for
Exercise 7.1.3(a)This function uses a trick that first appeared in Section 6.4.2, where we operated upon a tree by modifying the tree to remove one node at a time. Here, we could have written a function that tests whether a given course is present in a list of courses, and used that in the function enrollment. Instead, we have chosen to write only one function, which, when it does not find the desired course c at the head of the list of courses, calls itself recursively with the head of the course list removed. The first two cases of this function handle the situations where the list of courses is empty (when c is surely not among them), and where the head of the list equals c (when c surely is among the courses).
val A = Array.array(20, nil : real list);
Array.sub(A,29);
Array.update(A, 10, 43);
open Array;
(* swap exchanges A[i] with A[j] *)
fun swap(A,i,j) =
let
val temp = sub(A,i)
in
(update(A,i,sub(A,j)); update(A,j,temp))
end;
(* insert(A,i) pushes A[i] left until it finds an array element
smaller than it. i.e., insert(A,i) inserts A[i] into its
proper place in a sorted array A[0]...A[i-1] *)
fun insert(A,0) = ()
| insert(A,i) =
if sub(A,i-1) >= sub(A,i) then
(swap(A,i-1,i); insert(A,i-1))
else ();
(* isort1(A,i,n) inserts A[i]...A[n-1] into the sorted array
A[0]...A[i-1] *)
fun isort1(A,i,n) =
if i>=n then ()
else (insert(A,i); isort1(A,i+1,n));
(* An insertion-sort function *)
fun isort(A,n) = isort1(A,1,n);
Download this program
(* cycle1 moves positions i,...,n-1 of array A one position down *)
fun cycle1(A,n,i) =
if i >= n then ()
else (
Array.update(A,i-1,Array.sub(A,i));
cycle1(A,n,i+1)
);
fun cycle(A,n) =
let
val temp = Array.sub(A,0)
in
(
cycle1(A,n,1);
Array.update(A,n-1,temp)
)
end;
Download this program
(* rev1 reverses A[i] through A[n-i-1] *)
fun rev1(A,n,i) =
if 2*i+1 >= n then ()
else
let
val temp = Array.sub(A,i);
in
(
Array.update(A,i,Array.sub(A,n-i-1));
Array.update(A,n-i-1,temp);
rev1(A,n,i+1)
)
end;
fun reverse(A,n) = rev1(A,n,0);
Download this program
val i = ref 10;
i := 20;
(!x+!y)*(!x+!y);
datatype 'a linkedList = Nil |
Cell of {element: 'a, next: 'a linkedList ref};
For instance, a cell with element 1 and a nil next pointer
could be defined by
val c1 = Cell{element=1, next= ref Nil};
Notice that no parentheses are needed around the argument of a
Cell data constructor, because the curly braces group its
argument properly.
fun skip Nil = raise BadCell
| skip(Cell{next = ref Nil,...}) = raise BadCell
| skip(Cell{next = x as ref(Cell{next=y,...}),...}) =
x := !y;
Download code for Exercise 7.3.5(a,c)
datatype 'a bucket = Empty | Deleted | Filled of 'a;
(* search for x starting at bucket i, but not passing bucket j.
Here and elsewhere, n is the number of buckets. *)
fun lookup1(A,i,j,n,x) =
if Array.sub(A,i) = Filled(x) then true
else if Array.sub(A,i) = Empty then false
else if i=j then false (* we have searched the whole
hash table *)
else lookup1(A,(i+1) mod n,j,n,x);
(* lookup x in hash table A of n buckets, using hash function h *)
fun lookup(A,h,n,x) = lookup1(A,h(x),(h(x)-1) mod n,n,x);
(* delete1 deletes x from A; parameters are as for lookup1 *)
fun delete1(A,i,j,n,x) =
if Array.sub(A,i) = Filled(x) then
Array.update(A,i,Deleted)
else if Array.sub(A,i) = Empty then () (* x cannot be
in the hash table *)
else if i=j then () (* we have searched all buckets and
not found x *)
else delete1(A,(i+1) mod n,j,n,x);
(* delete takes parameters like lookup *)
fun delete(A,h,n,x) = delete1(A,h(x),(h(x)-1) mod n,n,x);
exception NoMoreRoom;
(* insert1 is analogous to lookup1 *)
fun insert1(A,i,j,n,x) =
if Array.sub(A,i) = Empty orelse Array.sub(A,i) = Deleted then
Array.update(A,i,Filled(x))
else if i=j then raise NoMoreRoom
else insert1(A,(i+1) mod n,j,n,x);
(* insert is analogous to lookup *)
fun insert(A,h,n,x) = insert1(A,h(x),(h(x)-1) mod n,n,x);
Download this program
open Array;
fun pivot(M,m,n) =
if m>=n then 0.0
else if m=n-1 then sub(sub(M,m),m)
else (* 0<m<n-1 *) (
let (* normalize row m to right of diagonal *)
val i = ref (m+1);
val a = sub(sub(M,m),m)
in
while !i<n do (
update(sub(M,m), !i, sub(sub(M,m),!i)/a);
i := !i + 1
)
end;
let (* subtract M[i,m]*M[m,j] from M[i,j]
for all i and j such that m<i,j<n *)
val i = ref (m+1);
val j = ref (m+1)
in
while !i<n do (
while !j<n do (
update(sub(M,!i),!j,sub(sub(M,!i),!j)-
sub(sub(M,!i),m)*sub(sub(M,m),!j));
j := !j + 1
);
j := m + 1;
i := !i + 1
)
end;
(* result is M[m,m] times recursive call on matrix
starting at row and column m+1 *)
sub(sub(M,m),m)*pivot(M,m+1,n)
);
Download this program
fun matrix(n,m,v:real) =
let
val M = Array.array(n,Array.array(m,v));
val i = ref 1
in
(
while !i<n do (
Array.update(M,!i,Array.array(m,v));
i := !i + 1
);
M
)
end;
A matrix is an array of arrays.
Notice that when we initialize a matrix we have to create a new array
for each row of the matrix, which we do in the while-loop.
Download this program
Exercise 7.5.6(a)
for(1,10,fn x=>(print(Int.toString x); print " "));