(**** LECTURE 4: Lists ****) (* $Id: lists.ML,v 1.1 1997/10/14 13:34:47 lcp Exp lcp $ *) (** 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 5: 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*) infix mem; fun x mem [] = false | x mem (y::l) = (x=y) orelse (x mem l); (*insert the list of xs into the ys, adding no duplicates*) fun union([],ys) = ys | union(x::xs, ys) = union(xs, if x mem ys then ys else x::ys); fun inter([],ys) = [] | inter(x::xs, ys) = if x mem 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