(**** LECTURE 3: Lists ****)
(** Selector and destructors **)
fun null [] = true
| null (_::_) = false;
fun hd (x::_) = x;
fun tl (_::xs) = xs;
(** length of a list **)
fun nlength [] = 0
| nlength (x::xs) = 1 + nlength xs;
(** append, or list concatenation **)
fun append ([], ys) = ys
| append (x::xs, ys) = x :: append(xs,ys);
(*Naive reverse -- QUADRATIC time*)
fun nrev [] = []
| nrev(x::xs) = (nrev xs) @ [x];
(** iterative definitions **)
fun addlen (n, [ ]) = n
| addlen (n, x::l) = addlen (n+1, l);
fun length l = addlen(0,l);
fun revApp ([], ys) = ys
| revApp (x::xs, ys) = revApp (xs, x::ys);
(*Fast-reverse -- actually, rev is an ML built-in function*)
fun rev xs = revApp(xs,[]);
(**** LECTURE 4: More Lists ****)
(** take and drop **)
(*not iterative, but it doesn't matter!*)
fun take ([], _) = []
| take (x::xs, i) = if i>0 then x :: take(xs, i-1)
else [];
fun drop ([], _) = []
| drop (x::xs, i) = if i>0 then drop (xs, i-1)
else x::xs;
(** zip and unzip **)
fun zip (x::xs,y::ys) = (x,y) :: zip(xs,ys)
| zip _ = [];
fun unzip [] = ([],[])
| unzip((x,y)::pairs) =
let val (xs,ys) = unzip pairs
in (x::xs, y::ys) end;
(** simple "set" operations -- equality type variables **)
(*membership in a list*)
fun member(x, []) = false
| member(x, y::l) = (x=y) orelse member(x,l);
(*insert the list of xs into the ys, adding no duplicates*)
fun union([],ys) = ys
| union(x::xs, ys) = union(xs, if member(x,ys) then ys else x::ys);
fun inter([],ys) = []
| inter(x::xs, ys) =
if member(x,ys) then x::inter(xs, ys)
else inter(xs, ys);
(** making change (with unlimited supplies of coins) **)
(*Make change for the amount*)
fun change1 (till, 0) = []
| change1 (c::till, amt) =
if amt