(**** LECTURE 10: Functions as Values ****) (fn n => n*2) 17; val prefix = (fn a => (fn b => a^b)); val promote = prefix "Professor "; map promote ["Paulson", "Mop"]; val dub = prefix "Sir "; fun insort lessequal = let fun ins (x, []) = [x] | ins (x, y::ys) = if lessequal(x,y) then x::y::ys else y :: ins (x,ys) fun sort [] = [] | sort (x::xs) = ins (x, sort xs) in sort end; insort (op<=) [5,3,7,5,9,8]; insort (op>=) [5,3,7,5,9,8]; fun sum f 0 = 0.0 | sum f m = f(m) + sum f (m-1); sum (fn k => real (k*k)) 5; fn (h,m,n) => sum (fn i=> sum (fn j=>h(i,j)) n) m; fn (f,m) => sum (sum f) m; (**** LECTURE 11: List Functionals ****) (*** The list functional MAP, with examples ***) fun sillylist [] = [] | sillylist (s::ss) = (s ^ "ppy") :: sillylist ss; fun double n = n*2; fun ddouble [] = [] | ddouble ([]::ls) = [] :: ddouble ls | ddouble ((x::l)::ls) = let val (l'::ls') = ddouble (l::ls) in (x*2::l')::ls' end; ddouble[[1], [2,3], [4,5,6], [], [7]]; (*matrix transpose*) fun transp ([]::_) = [] | transp rows = (map hd rows) :: transp (map tl rows); (*vector dot product (curried) *) fun dotprod [] [] = 0.0 | dotprod (x::xs) (y::ys) = x*y + dotprod xs ys; (*matrix product*) fun matprod(Arows,Brows) = let val cols = transp Brows in map (fn row => map (dotprod row) cols) Arows end; val Arows = [ [2.0, 0.0], [3.0, ~1.0], [0.0, 1.0], [1.0, 1.0] ] and Brows = [ [1.0, 0.0, 2.0], [4.0, ~1.0, 0.0] ]; matprod(Arows,Brows); (** The list functionals EXISTS and FORALL **) fun exists p [] = false | exists p (x::xs) = (p x) orelse exists p xs; fun all p [] = true | all p (x::xs) = (p x) andalso all p xs; (*example: the membership predicate*) fun member(y,xs) = exists (fn x => x=y) xs; (*** The list functional FILTER ***) fun filter p [] = [] | filter p (x::xs) = if p(x) then x :: filter p xs else filter p xs; (*example: the intersection of two "sets"*) fun inter(xs,ys) = filter (fn x => x mem ys) xs; (*** The FOLD functionals **) (* (op+) (e, [x1,...,xn]) ==> ((e+x1)+x2) ...+xn *) fun foldl f (e, []) = e | foldl f (e, x::xs) = foldl f (f(e,x), xs); (* (op+) ([x1,...,xn], e) ==> x1+(x2 ...+(xn+e)) *) fun foldr f ([], e) = e | foldr f (x::xs, e) = f(x, foldr f (xs,e)); (*summing a list of lists, creating no intermediate list!*) foldl (foldl op+) (0, [[1], [2,3], [4,5,6]]); (*list reversal and length functions*) foldl (fn (e,x) => x::e) ([], [1,2,3,4]); foldl (fn (e,x) => e+1) (0, [1,2,3,4]); (*defining append and map*) foldr op:: ([1,2],[3,4]); foldr (fn(x,e)=> x div 2 :: e) ([4,6,8],[]);