(* 'eg.sml' some standard functions often used in functional programming *) (* NB. They may differ slightly from those in the 'List' structure. *) fun hd (h::_) = h; fun tl (_::t) = t; fun null [] = true | null _ = false; fun range lo hi = let fun r lo = if lo > hi then [] else lo::r (lo+1) in r lo end; fun length [] = 0 | length (_::xs) = 1 + length xs; fun append [] ys = ys (* or infix @ *) | append (x::xs) ys = x::append xs ys; fun take _ [] = [] | take n (x::xs) = if n > 0 then x::take (n-1) xs else []; fun drop _ [] = [] | drop n (xxs as (_::xs)) = if n > 0 then drop (n-1) xs else xxs; fun curry fu x y = fu(x,y); fun uncurry fc(x,y) = fc x y; fun flip f x y = f y x; fun map _ [] = [] | map f (x::xs) = (f x)::(map f xs); fun transpose ([]::_) = [] | transpose m = map hd m::transpose(map tl m); fun catOption [] = [] | catOption ((SOME x)::xs) = x::catOption xs | catOption ( NONE ::xs) = catOption xs; fun filter p [] = [] | filter p (x::xs) = if p x then x::filter p xs else filter p xs; fun foldl f z [] = z | foldl f z (x::xs) = foldl f (f z x) xs; fun foldr f z [] = z | foldr f z (x::xs) = f x (foldr f z xs); fun zip (x::xs) (y::ys) = (x,y)::(zip xs ys) | zip _ _ = []; (* zip, input a pair of lists, output a list of pairs *) fun unzip [] = ([], []) | unzip ((x,y)::xys) = let val (xs,ys) = unzip xys in (x::xs,y::ys) end; fun zipWith f (x::xs) (y::ys) = (f x y)::(zipWith f xs ys) | zipWith _ _ _ = []; fun twice f = f o f; datatype 'et Tree = EmptyTree | Fork of ('et Tree) * 'et * ('et Tree) fun height EmptyTree = 0 | height (Fork(L,e,R)) = 1 + Int.max(height L, height R);