let rec appartient e l =
  match l with
    [] -> false
  |a::_ when a=e -> true
  |_::q -> appartient e q
;;

let rec elimine_doublon l =
  match l with
    [] -> []
  |a::q -> if (appartient a q) then elimine_doublon q
      else a::(elimine_doublon q)
;;

let rec second l =
  match l with
    [] -> []
  |(x,y)::reste -> x::second reste;;
;;


module type tFILE = sig
  type 'a t
  val vide : 'a t
  val enfile : 'a -> 'a t -> 'a t
  val defile : 'a t -> 'a t
  val sommet : 'a t -> 'a
  val est_vide : 'a t -> bool
end


module FILE : tFILE	= struct

  type 'a t = 'a list
  let vide = []

  let enfile = fun a -> fun file -> match file with
    | [] -> [a]
    | x::reste -> x::reste @ [a];;

  let defile = fun file -> match file with
    | [] -> failwith "empty file"
    | x::reste -> reste;;

  let sommet = fun file -> match file with
    | [] -> failwith "empty file"
    | x::reste -> x;;

  let est_vide = fun file -> file = [];;
end


module type tFILE_AUX = functor (F:tFILE) -> sig
  val enfile_elems : 'a list -> 'a F.t -> 'a F.t
end

module FILE_AUX : tFILE_AUX = functor(F:tFILE) -> struct

  let  rec enfile_elems liste file = match liste with
    |[] -> file
    |x::reste -> F.enfile x (enfile_elems reste file)
end

module type tGRAPH = sig

  (* graphe paramétré par le type de ses sommets *)
  type 's t
  (* construit un graphe en fournissant la liste des arcs
     (origine, destination) présents dans le graphe *)
  val cons : ('s * 's) list -> 's t
  (* renvoie la liste (sans répétition) de tous les sommets impliqués
     dans le graphe *)
  val sommets : 's t -> 's list
  (* pour un sommet donné et un graphe donné,
renvoie la liste (sans répétition) des sommets successeurs *)
  val succ : 's -> 's t -> 's list
end

module GRAPH : tGRAPH	= struct
  type 's t = ('s  * 's)list;;

  let  cons = function
    |[]->[]
    |(x1,x2)::reste -> (x1,x2)::reste ;;

  let rec sommets = function
    |[]->[]
    |(x1,x2)::reste -> if (appartient x1 (second reste)) then sommets reste else x1::(sommets reste);;

  let rec succ s = function
    |[]->[]
    |(x1,x2)::reste -> let aux = if x1 = s then x1::(succ s reste) else succ s reste
        in elimine_doublon  aux;;

end