interval thing

type ('a, 'b) choice = Left of 'a | Right of 'b

type debut = Debut of float
type fin = Fin of float

let cmp a b =
  match a, b with
  | Left (Debut x), Left (Debut y)
  | Left (Debut x), Right (Fin y)
  | Right (Fin x), Left (Debut y)
  | Right (Fin x), Right (Fin y) -> Float.compare x y

type interval = Interval of debut * fin

let rec explode is =
  match is with
  | [] -> []
  | Interval (d, f) :: is -> [Left d; Right f] @ explode is

let mesh iss = List.sort cmp (List.fold_left (fun acc elem -> explode elem @ acc) [] iss)

let rec combine' n m depth mesh =
  match mesh with
  | [] -> []
  | Left (Debut x' as x) :: xs ->
    if depth = n - 1 then
      Left x :: combine' n m (depth + 1) xs
    else if depth = m then
      Right (Fin x') :: combine' n m (depth + 1) xs
    else
      combine' n m (depth + 1) xs
  | Right (Fin x' as x) :: xs ->
    if depth = n then
      Right x :: combine' n m (depth - 1) xs
    else if depth = m + 1 then
      Left (Debut x') :: combine' n m (depth - 1) xs
    else
      combine' n m (depth - 1) xs

let rec mkintervals mesh =
  match mesh with
  | [] -> []
  | Left d :: Right f :: delims -> Interval (d, f) :: mkintervals delims
  | _ -> failwith "IMPOSSIBLE!!!"

(* This is the main function. n and m are optional parameters, where n is the lower bound and m the upper. *)
let combine ?(n = 1) ?(m = Int.max_int) iss = mkintervals (combine' n m 0 (mesh iss))