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

(* let l = C(1, C(2, C(3, Nil))) *)

let rec length l =
  match l with
    Nil -> 0
  | C(_, tl) -> 1 + length tl

let length_rt l =
  let rec aux l c =
    match l with
      Nil -> c
    | C(_, tl) -> aux tl (succ c) in
  aux l 0
      
let rec make_list x n =
  if n = 0 then Nil
  else C(x, make_list x (pred n))

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 concat l1 l2 =
  match l1 with
    Nil -> l2
  | C(e, tl) -> C(e, concat tl l2)

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

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

let fact n = fact_aux n 1

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

let reverse l = (* O(len(l)) *)
  let rec aux l r =
    match l with
      Nil -> r
    | C(e, tl) -> aux tl (C(e, r)) in
  aux l Nil

let rec reverse l = (* O(len(l)^2 *)
  match l with
    [] -> []
  | e :: tl -> reverse tl @ [e]

let reverse_rt l = (* O(len(l)) *)
  let rec aux l r =
    match l with
      [] -> r
    | e :: tl -> aux tl (e :: r) in
  aux l []

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