type pair = P of int * int

let pair_cmp pair =
  let P(x,y) = pair in
  if x > y then 1 else if x < y then -1 else 0

let pair_cmp pair =
  match pair with
    P(x,y) ->
    if x > y then 1 else if x < y then -1 else 0

let pair_cmp pair =
  match pair with
    P(x,y) when x > y -> 1
  | P(x,y) when x < y -> -1
  | _ -> 0

let pair_cmp = function
    P(x,y) when x > y -> 1
  | P(x,y) when x < y -> -1
  | _ -> 0

let time f =
  let start = Sys.time () in
  let _ = f () in
  Sys.time () -. start

let rec iota_quadratique n = (* O(n^2) *)
  if n = 0 then []
  else iota_quadratique (pred n) @ [pred n]

let iota n = (* O(n) *)
  let rec aux i =
    if i = n then []
    else i :: aux (succ i) in
  aux 0

let iota_rt n = (* O(n) *)
  let rec aux n l =
    if n = -1 then l
    else aux (pred n) (n :: l)
  in aux (pred n) []

let _ = List.init
          10
          (let l = ref [] in (fun i ->
               begin
                 l := 0 :: !l;
                 !l;
                 end))
                                  

let rec filter pred l =
  match l with
    [] -> []
  | e :: tl -> let r = filter pred tl in
               if pred e then e :: r
               else r

let filter_rt pred l =
  let rec aux l r =
    match l with
      [] -> r
    | e :: tl -> if pred e then aux tl (e :: r)
                 else aux tl r
  in List.rev (aux l [])

let filter pred l =
  let r = ref [] in
  begin
    List.iter (fun e -> if pred e then r := e :: !r) l;
    List.rev !r;
  end

let length_left l =
  List.fold_left (fun x y -> x + 1) 0 l

let length_right l =
  List.fold_right (fun x y -> y + 1) l 0