(* The procedures below work on lists of any type *)

 (* Length of a list *)
 let rec length  = function
   |[] -> 0
   |x::xs -> 1 + length xs;;

 (* Insertion sort *)
 (* An order relation must exist *)
 let rec sort = function
   |[] -> []
   |x::xs -> insert x (sort xs)
 and insert e = function
   |[] -> [e]
   |x::xs -> if x > e 
             then e::x::xs 
             else x::(insert e xs);;

 # let l =
 ["The"; "quick"; "brown"; "fox"; "jumps"; "over"; "the"; "lazy"; "dog"];

 # length l;;
 - : int = 7

 # sort l;;
 - : string list = 
 ["The"; "brown"; "dog"; "fox"; "jumps"; "lazy"; "over"; "quick"; "the"]

 (* Definition of a binary tree, of any type 'a *)
 type 'a tree = Node | Tree of ('a tree * 'a * 'a tree) ;;

 let a = Tree(Node, 4, Tree(Node, 2, Node)) ;;
 
 (* Height of a tree *)
 let rec height = function
   |Node -> 0
   |Tree(left, _, right) -> 1 + max (height left) (height right)  ;;

 # height a;;
 - : int = 2

 let rec dicho f min max eps =
   let fmin = f min and fmax = f max in
     if fmin *. fmax > 0.
     then failwith "No root"
     else if max -. min < eps then (min, max) (* return an interval *)
     else let mid = (min +. max) /. 2. in
       if (f mid) *. fmin < 0.
       then dicho f min mid eps
       else dicho f mid max eps ;;

 (* Approximation of the square root of 2 *)
 # dicho (fun x -> x *. x -. 2.) 0. 10. 0.000000001;;
 - : float * float = (1.4142135618, 1.41421356238)