let rec square_list_naive l =
  match l with
    [] -> []
  | e :: tl -> e * e :: square_list_naive tl

let square_list l =
  let rec aux l lc =
    match l with
      [] -> lc
    | e :: tl -> aux tl (e * e ::  lc)
  in List.rev (aux l [])

let cube_list l =
  let rec aux l lc =
    match l with
      [] -> lc
    | e :: tl -> aux tl (e * e * e ::  lc)
  in List.rev (aux l [])

let f_list f l =
  let rec aux l lc =
    match l with
      [] -> lc
    | e :: tl -> aux tl (f e ::  lc)
  in List.rev (aux l [])

let square_list l = List.map (fun x -> x * x) l

let rec find_if pred l =
  match l with
    [] -> None
  | e :: tl -> if pred e then Some e
               else find_if pred tl

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) 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_quad n = (* O(n^2) *)
  if n = 0 then []
  else iota_quad (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 filter pred l =
  let r = ref [] in
  begin
    List.iter (fun e -> if pred e then r := e :: !r) l;
    List.rev !r
  end