(* Function composition *)
let (++) f g x = f (g x);;

let findi p =
 let rec aux n = function
 | [] -> raise Not_found
 | x::_ when p x -> n, x
 | _::xs -> aux (n+1) xs
 in aux 0
;;

let option_map f = function
 | None -> None
 | Some x -> Some (f x)
;;

let option_get = function
 | Some x -> x
 | None -> failwith "option_get: None"
;;

let rec find_opt f =
 function
    [] -> None
  | x::xs ->
     match f x with
        None -> find_opt f xs
      | Some _ as res -> res

let rec index_of ?(eq=(=)) x =
 function
    [] -> raise Not_found
  | y::_ when eq x y -> 0
  | _::l -> 1 + index_of ~eq x l

let index_of_opt ?eq l t =
 try
  Some (index_of ?eq t l)
 with
  Not_found -> None
;;

let rec filter_map f =
 function
    [] -> []
  | hd::tl ->
     match f hd with
        None -> filter_map f tl
      | Some x -> x::filter_map f tl
;;

(* the input must be sorted *)
let rec first_duplicate =
 function
    []
  | [_] -> None
  | x::y::_ when x=y -> Some x
  | _::tl -> first_duplicate tl

(* the input must be sorted
   output: list of non duplicates; list of duplicates *)
let rec split_duplicates =
 function
    [] -> [],[]
  | [x] -> [x],[]
  | x::(y::_ as tl) ->
     let nondup,dup = split_duplicates tl in
     if x = y then
      List.filter ((<>) x) nondup, x::dup
     else
      x::nondup,dup

(* Non c'e' nella vecchia versione di OCaml :( *)
let uniq ?(compare=compare) =
  let rec aux = function
  | [] -> []
  | [_] as ts -> ts
  | t1 :: (t2 :: _ as ts) ->
    if compare t1 t2 = 0 then aux ts else t1 :: (aux ts)
  in aux

let sort_uniq ?(compare=compare) l = uniq ~compare (List.sort compare l)

let rec list_cut = function
  | 0, lst -> [], lst
  | n, x::xs -> let a, b = list_cut (n-1,xs) in x::a, b
  | _ -> assert false
;;

let concat_map f l = List.concat (List.map f l);;

let rec take n =
 function
 | [] -> assert (n = 0); []
 | _ when n = 0 -> []
 | x::xs -> x::(take (n-1) xs)
;;

module Vars =
struct

let string_of_var v =
  if v > 25
     then "`" ^ string_of_int v
     else String.make 1 (char_of_int (v + int_of_char 'a'))
;;

let var_of_string s =
 if String.length s <> 1 then (
   if s.[0] = '`' then int_of_string (String.sub s 1 (-1 + String.length s)) else assert false
 ) else int_of_char s.[0] - int_of_char 'a'

let print_name l n =
 if n = -1
  then "*"
  else if n >= List.length l then "x" ^ string_of_int (List.length l - n - 1) else List.nth l n

end