(* '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);