(* DIVERSE LISTENFUNKTIONEN *)
(* L. Fellermayr *)

exception Empty_List ;;

(* Kopfelement und Rest einer Liste *)

let hd (h::t) = h ;;
let tl (h::t) = t ;;

(* Ermittle, ob Liste leer ist *)

let null l = l = [] ;;

(* Laenge einer Liste, vgl. List.length *)

let len =
  let rec len_aux acc = function
    []   -> acc
  | h::t -> len_aux (acc+1) t
in len_aux 0 ;;

(* Revertiere Liste "clever" *)

let rev =
  let rec rev_aux acc = function
      []   -> acc
    | h::t -> rev_aux (h::acc) t
in rev_aux [] ;;

(* Berechne Durchschnitt einer int-Liste *)

let avg =
  let rec adder acc1 acc2 = function
      []   -> float_of_int acc1 /. float_of_int acc2
    | h::t -> adder (acc1+h) (acc2+1) t
in adder 0 0 ;;

(* Suche Extremum *)

let rec extremum f = function
    []      -> raise Empty_List
  | h::[]   -> h
  | h::i::t -> if f h i then extremum f (h::t) else extremum f (i::t) ;;

let max = extremum (fun x y -> x > y) ;;
let min = extremum (fun x y -> x < y) ;;

(* Mapping *)

let map_tailrec =
  let rec map_aux acc f = function
      []   -> rev acc
    | h::t -> map_aux ((f h)::acc) f t
in map_aux []

let rec map_linrec f = function
    [] -> []
  | h::t  -> (f h) :: (map_linrec f t) ;;

(* Praedikaten-Filter *)

let rec pfilter f = function
    []   -> []
  | h::t -> if (f h) then h::(pfilter f t) else pfilter f t ;;

(* Beispielanwendung fuer pfilter: ungerade Zahlen extrahieren *)

let extractOdds = pfilter (fun x -> x mod 2 <> 0) ;;

(* Liste der Laenge length aus Element x erzeugen *)

let mklist x length =
  let rec mklist_aux c cl =
    if (c < length) then mklist_aux (c+1) (x::cl) else cl
in mklist_aux 0 [] ;;

(* QuickSort *)

let rec qs l = match l with
    (x::xs) -> qs (pfilter (fun z -> z <  x) xs) @ [x] @
               qs (pfilter (fun z -> z >= x) xs)
  | [] -> [];;

(* realize associative lists *)

let rec assoc n = function
    []        -> raise Not_found
  | (k,v)::xs -> if (n = k) then v else assoc n xs ;;

(* tabulate *)

let tabulate f n =
  let rec tab_aux c acc =
    if c > 0 then tab_aux (c-1) ((f c)::acc) else acc
  in tab_aux n [] ;;

(* map list values *)

let rec map f = function
    [] -> []
  | x::xs -> (f x) :: map f xs ;;

(* EOF *)