type 'a my_list =
    | Item of ('a * 'a my_list)
    | None

(** Return the length (number of elements) of a given list. *)
let length my_list =
    let rec aux l n =
        match l with
        | Item (_, tl) -> aux tl (n + 1)
        | None -> n
    in aux my_list 0

(** Return the first element of the given list.
 * Raise [Failure "hd"] if the list is empty.
 *)
let hd = function
    | Item (h, _) -> h
    | None -> raise (Failure "hd")

(** Return the given list without its first element.
 * Raise [Failure "tl"] if the list is empty.
 *)
let tl = function
    | Item (_, t) -> t
    | None -> raise (Failure "Called tail on empty list")

(** Return the n-th element of the given list.
 * Raise [Failure "hd"] or [Failure "tl"] if the list is too short.
 * Raise [Invalid_argument "my_list.nth"] if n is negative.
 *)
let rec nth my_list n =
    match n with
    | _ when n < 0 -> raise (Invalid_argument "my_list.nth")
    | 0 -> (hd my_list)
    | _ -> (nth (tl my_list) (n - 1))

(** Return the given list in the reverse order. *)
let rev my_list =
    let rec aux my_list agg =
        match my_list with
        | Item(hd, tl) -> aux tl (Item(hd, agg))
        | None -> agg
    in aux my_list None

(** Return a list containing the result of f(x) for each element x in the given
 * list. *)
let rec map f my_list =
    match my_list with
    | Item(hd, tl) -> Item(f hd, map f tl)
    | None -> None

(** Return a list containing only the elements x in the given list for which
 * f(x) returns true.
 *)
let rec filter f my_list =
    match my_list with
    | None -> None
    | Item(hd, tl) -> (
        match f hd with
        | true -> Item(hd, filter f tl)
        | _ -> filter f tl
    )

(** Return a list which results in the concatenation of l1 and l2. *)
let rec append l1 l2 =
    match l1 with
    | Item(hd, tl) -> Item(hd, (append tl l2))
    | None -> l2

(** Return a list which results in the concatenation of reversed l1 and l2. *)
let rev_append l1 l2 =
    append (rev l1) l2

(** Return a list consisting of the contenation of the given list of lists. *)
let rec flatten = function
    | Item(hd, tl) -> append hd (flatten tl)
    | None -> None