(*
   val factorial : int -> int = <fun>
   val length : 'a list -> int = <fun>
   val take : int -> 'a list -> 'a list = <fun>
   val drop : int -> 'a list -> 'a list = <fun>
   val sort_insert : 'a -> 'a list -> 'a list = <fun>
   val sort : 'a list -> 'a list = <fun>
   val merge : ('a -> 'a -> bool) -> 'a list -> 'a list -> 'a list = <fun>
   val split : 'a list -> 'a list -> 'a list -> 'a list * 'a list = <fun>
   val mergesort : ('a -> 'a -> bool) -> 'a list -> 'a list = <fun>
   val map : ('a -> 'b) -> 'a list -> 'b list = <fun>
*)
let rec factorial a =
  match a with
  | 1 -> 1
  | _ -> a * factorial (a - 1)

let rec length l =
  match l with
  | [] -> 0
  | _ :: t -> 1 + length t

let rec take n l =
  match n with
  | 0 -> []
  | _ -> match l with
    | [] -> []
    | h :: t -> h :: take (n - 1) t

let rec drop n l =
  match n with
  | 0 -> l
  | _ -> match l with
    | [] -> []
    | h :: t -> drop (n - 1) t

let rec sort_insert x l =
  match l with
  | [] -> [x]
  | h :: t ->
    if x <= h
    then x :: h :: t
    else h :: sort_insert x t

let rec sort l =
  match l with
  | [] -> []
  | h :: t -> sort_insert h (sort t)

let rec merge cmp x y =
  match (x, y) with
  | ([], _) -> y
  | (_, []) -> x
  | (h1 :: t1, h2 :: t2) ->
    if cmp h2 h1
    then h1 :: (merge cmp t1 y)
    else h2 :: (merge cmp x t2)

and split x y z =
  match x with
  | [] -> (y, z)
  | x :: resto -> split resto z (x :: y)

and mergesort cmp x =
  match x with
  | ([] | _ :: []) -> x
  | _ -> let (pri, seg) = split x [] []
    in (merge cmp (mergesort cmp pri) (mergesort cmp seg))

let rec map f l =
  match l with
  | [] -> []
  | h::t -> f h :: map f t