(**** Sample programs for the course FOUNDATIONS OF COMPUTER SCIENCE by Lawrence C. Paulson LECTURES 14-15 \$Id: proc.ML,v 1.1 1997/10/14 13:34:47 lcp Exp lcp \$ ****) (**** LECTURE 14: Elements of Procedural Programming ****) val p = ref 5; val ps = [ref 77, p]; p := !p + 1; hd ps := 3; ps; fun length xs = let val lp = ref xs and np = ref 0 in while not (null (!lp)) do (lp := tl (!lp); np := 1 + !np); !np end; fun makeAccount (initBalance: int) = let val balance = ref initBalance fun withdraw amt = if amt > !balance then !balance else (balance := !balance - amt; !balance) in withdraw end; val student = makeAccount 500; val director = makeAccount 400000; student 5; (*coach fare*) director 50000; (*Jaguar*) fun insert (A,kp,x) = let val ip = ref (!kp) in while !ip>0 do (Array.update(A, !ip, Array.sub(A, !ip-1)); ip := !ip-1); Array.update(A, 0, x); kp := !kp+1 end; val A = Array.array(9,9) and kp = ref 0; insert (A,kp,1); insert (A,kp,2); insert (A,kp,3); insert (A,kp,4); Array.foldr (op::) [] A; (**** LECTURE 15: Linked Data Structures ****) (** Mutable lists **) datatype 'a mlist = Nil | Cons of 'a * 'a mlist ref; fun mlistOf [] = Nil | mlistOf (x::l) = Cons (x, ref (mlistOf l)); (*building a list from the rear!*) fun extend (mlp, x) = let val tail = ref Nil in mlp := Cons (x, tail); tail end; val mlp = ref (Nil: string mlist); extend (mlp, "a"); extend (it, "b"); extend (it, "c"); mlp; (*Pure effect*) fun joining (mlp, ml2) = case !mlp of Nil => mlp := ml2 | Cons(_,mlp1) => joining (mlp1, ml2); (*Effect and value*) fun join (ml1, ml2) = let val mlp = ref ml1 in joining (mlp, ml2); !mlp end; join(Nil, mlistOf[1,2,3]); join(mlistOf[1,2,3], mlistOf[4,5]); join(mlistOf[1,2,3], Nil); val ml = mlistOf [3,5,9]; (*cyclic list*) val ml = mlistOf [0,1]; join(ml,ml); val ml1 = mlistOf ["a"]; val ml2 = mlistOf ["b","c"]; join(ml1,ml2); (*ml1 has been changed; ml2 has not*) ml1; ml2; fun reversing (prev, ml) = case ml of Nil => prev | Cons(_,mlp2) => let val ml2 = !mlp2 in mlp2 := prev; reversing (ml, ml2) end; fun reversing (prev, Nil) = prev | reversing (prev, ml as Cons(_,mlp2)) = let val ml2 = !mlp2 in mlp2 := prev; reversing (ml, ml2) end; fun drev ml = reversing (Nil, ml); drev (mlistOf (explode "hello")); val ml = mlistOf (explode "hello"); drev ml; ml; val ml = mlistOf [3, 5, 9]; drev ml; ml;