module type DICTIONNAIRE =
sig
  type ('a, 'b) t
  val creer : unit -> ('a,'b) t
  val ajouter :
    'a -> 'b -> ('a,'b) t -> ('a,'b) t
  val acceder : 'a -> ('a,'b) t -> 'b
  val appartient : 'a -> ('a,'b) t -> bool
  val supprimer :
    'a -> ('a,'b) t -> ('a,'b) t
end

module Dictionnaire : DICTIONNAIRE =
  struct

    type ('a, 'b) t =
        Vide
      | Element of
          'a * 'b * ('a,'b) t

    exception Pas_presente

    let creer = fun () -> Vide

    let rec ajouter =
      fun x y d ->
      match d with
        Vide -> Element (x,y,d)
      | Element (x',y',d') when x = x' ->
        Element (x', y, d')
      | Element (x,y,d') ->
        Element(x,y, ajouter x y d')

    let rec acceder =
      fun x d ->
      match d with
        Vide -> raise Pas_presente
      | Element (x',y,d') when x = x' -> y
      | Element (_ ,_ , d') -> acceder x d'

    let rec appartient =
      fun x d ->
      try
        let _ = acceder x d in true
      with Pas_presente -> false

    let rec supprimer =
      fun x d ->
      match d with
        Vide -> raise Pas_presente
      | Element (x',y,d') when x = x' -> d'
      | Element (x' ,y' , d') ->
        Element (x',y', supprimer x d')
end