(* Sample OCaml functions with recursion and higher-order functions *)

(* max : 'a -> 'a -> 'a
 * max a b is the largest value between a and b *)
let max a b = if a > b then a else b;;

(* listmax : 'a list -> 'a
 * listmax [a; b; c; ...] = max a, b, c, ...
 * Finds the maximum value inside a list *)
let rec listmax ls = match ls with
    [] -> raise Not_found
    | [a] -> a
    | h::t -> max h (listmax t);;

(* maxf : ('a -> 'b) -> 'a list -> 'b
 * maxf f [a; b; c] = max f(a), f(b), f(c), ...
 * Finds the maximum value of a function over a list *)
let rec maxf f = function
    [] -> raise Not_found
    | [a] -> f a
    | h::t -> max (f h) (maxf f t);;

(* compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b
 * (compose f g)(x) = f o g (x) = f(g(x))
 * Composes functions f and g together to get the composite fog function *)
let compose f g x = f (g x);;

(* d : (float -> float) -> float -> float
 * (d f)(x) = f'(x)
 * computes the approximate derivative of f *)
let d f x = (f (x +. 0.001) -. f x) /. 0.001;;

(* integral : (float -> float) -> float -> float -> float
 * integral f a b = [F(b) - F(a)] where f = F' (F is anti-derivative of f)
 * Computes the approximate area of f from point a to b *)
let integral f a b = (b -. a) /. 6. *. (f a +. 4. *. f ((a +. b) /. 2.) +. f b);;

(* map : ('a -> 'b) -> 'a list -> 'b list
 * map f [a; b; c; ...] = [f(a); f(b); f(c); ...]
 * maps function f to every element of list  *)
let rec map f l = match l with
    [] -> []
    | h::t -> (f h)::(map f t);;

(* filter : ('a -> bool) -> 'a list -> 'a list
 * filter even [1; 2; 3; 4] = [2; 4]
 * filters the list according to a guard condition given  *)
let rec filter f l = match l with
    [] -> []
    | h::t -> let t' = filter f t in if f h then h::t' else t';;

(* foldr : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b
 * foldr f z [a; b; c] = (f a (f b (f c z)))
 * folds function application on the right. Non-tail recursive *)
let rec foldr f z l = match l with
    [] -> z
    | h::t -> f h (foldr f z t);;

(* foldl : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
 * foldl f z [a; b; c] = (f (f (f z a) b) c)
 * folds function application on the left. Tail recursive *)
let rec foldl f z l = match l with
    [] -> z
    | h::t -> foldl f (f z h) t;;