type 'a mylist = Nil | C of 'a * 'a mylist

let rec make_list x n =
  if  n = 0 then
    Nil
  else
    C(x, make_list x (pred n))

let rec concat l1 l2 = (* O(length(l1)) *)
  match l1 with
    Nil -> l2
  | C(x, tl) -> C(x, concat tl l2)

let rec fact_aux n p =
  if n = 0 then p
  else fact_aux (pred n) (n * p)

let fact n = fact_aux n 1

let fact n = 
  let rec aux n p =
    if n = 0 then p
    else aux (pred n) (n * p)
  in aux n 1

let length_rt l =
  let rec aux l lg =
    match l with
      Nil -> lg
    | C(_, tl) -> aux tl (succ lg)
  in aux l 0

let make_list_rt x n =
  let rec aux n l =
    if n = 0 then l
    else aux (pred n) (C (x,l))
  in aux n Nil

let rec reverse l = (* O(length(l)^2 *)
  match l with
    Nil -> Nil
  | C(x, tl) -> concat (reverse tl) (C(x, Nil))

let reverse_rt l =
  let rec aux l rl =
    match l with
      Nil -> rl
    | C(x, tl) -> aux tl (C(x,rl))
  in aux l Nil

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) ->
    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