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

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

fun findName(n,L) = List.filter (fn (r:student) => (n = #name(r))) L;That is, we filter the list of student records

(* 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

val c1 = Cell{element=1, next= ref Nil};Notice that no parentheses are needed around the argument of a

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 " "));