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