Exercices

Listes d'association

1. Définir une signature ALIST déclarant un type (abstrait) paramétré par deux variables de type (une pour la clé, l'autre pour la valeur stockée), une fonction de création, une fonction d'ajout, une fonction d'accès, un test d'appartenance et une fonction de suppression.

   
   # module type ALIST =
     sig
      type ('a,'b) t
      val create : unit -> ('a,'b) t
      val add : 'a -> 'b -> ('a,'b) t ->  ('a,'b) t
      val get : 'a -> ('a,'b) t ->  'b
      val mem : 'a -> ('a,'b) t ->  bool
      val rem : 'a -> ('a,'b) t ->  ('a,'b) t
     end ;;
   module type ALIST =
     sig
       type ('a, 'b) t
       val create : unit -> ('a, 'b) t
       val add : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
       val get : 'a -> ('a, 'b) t -> 'b
       val mem : 'a -> ('a, 'b) t -> bool
       val rem : 'a -> ('a, 'b) t -> ('a, 'b) t
     end
   
   
   

   On choisira une implantation fonctionnelle (ie : sans effet de bord sur la donnée).
   
   
2. Définir le module Alist respectant la signature ALIST

   
   # module Alist:ALIST =
     struct
      type ('a,'b) t = ('a*'b) list
      let create () = []
      let add k v al = (k,v)::al
      let get = List.assoc
      let mem = List.mem_assoc
      let rem = List.remove_assoc
     end ;;
   module Alist : ALIST
   
   
   

   
   
   
3. Définir une signature ADM_ALIST pour l'administrateur des listes d'association. Il pourra uniquement créer une liste, y rajouter et en retirer une entrée.

   
   # module type ADM_ALIST =
     sig
      type ('a,'b) t
      val create : unit -> ('a,'b) t
      val add : 'a  -> 'b -> ('a,'b) t -> ('a,'b) t
      val rem : 'a -> ('a,'b) t -> ('a,'b) t
     end ;;
   module type ADM_ALIST =
     sig
       type ('a, 'b) t
       val create : unit -> ('a, 'b) t
       val add : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
       val rem : 'a -> ('a, 'b) t -> ('a, 'b) t
     end
   
   
   

   
   
   
4. Définir une signature USER_ALIST pour les utilisateurs des listes qui n'auront droit qu'à l'accès et au test d'appartenance.

   
   # module type USER_ALIST =
     sig
      type ('a,'b) t
      val get : 'a -> ('a,'b) t -> 'b
      val mem : 'a -> ('a,'b) t -> bool
     end ;;
   module type USER_ALIST =
     sig
       type ('a, 'b) t
       val get : 'a -> ('a, 'b) t -> 'b
       val mem : 'a -> ('a, 'b) t -> bool
     end
   
   
   

   
   
   
5. Créer deux modules AdmAlist et UserAlist pour les administrateurs et les utilisateurs. Penser qu'un utilisateur doit pouvoir manipuler une liste créée par un administrateur.

   
   # module AdmAlist = (Alist:ADM_ALIST with type ('a,'b) t = ('a,'b) Alist.t) ;;
   module AdmAlist :
     sig
       type ('a, 'b) t = ('a, 'b) Alist.t
       val create : unit -> ('a, 'b) t
       val add : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
       val rem : 'a -> ('a, 'b) t -> ('a, 'b) t
     end
   # module UserAlist = (Alist:USER_ALIST with type ('a,'b) t = ('a,'b) Alist.t) ;;
   module UserAlist :
     sig
       type ('a, 'b) t = ('a, 'b) Alist.t
       val get : 'a -> ('a, 'b) t -> 'b
       val mem : 'a -> ('a, 'b) t -> bool
     end
   
   
   

Vecteurs paramétrés

# module type NOMBRE =
  sig
   type a
   type t
   val create : a -> t
   val add : t -> t -> t
   val string_of : t -> string
  end ;;

1. Définir le foncteur FVecteur paramétré par un module de signature NOMBRE qui définit un type t, une fonction de création, l'addition (i.e. la translation) et la conversion en chaîne de caractères.

   
   # module  FVecteur (N:NOMBRE) =
     struct
      type e = N.t
      type t = { mutable vx:e; mutable vy:e }
      let create x0 y0 = { vx=x0; vy=y0 }
      let add v1 v2=  {vx = N.add v1.vx v2.vx; vy = N.add v1.vy v2.vy}
      let string_of v= "("^N.string_of v.vx^" , "^N.string_of v.vy^")"
     end ;;
   module FVecteur :
     functor(N : NOMBRE) ->
       sig
         type e = N.t
         and t = { mutable vx: e; mutable vy: e }
         val create : e -> e -> t
         val add : t -> t -> t
         val string_of : t -> string
       end
   
   
   

   
   
   
2. Définir une signature VECTEUR , non paramétrée, où les types des nombres et des vecteurs sont abstraits.

   
   # module type VECTEUR =
     sig
      type e
      type t
      val create : e -> e -> t
      val add :t -> t -> t
      val string_of : t -> string
     end ;;
   module type VECTEUR =
     sig
       type e
       and t
       val create : e -> e -> t
       val add : t -> t -> t
       val string_of : t -> string
     end
   
   
   

   
   
   
3. Définir trois structures Rationnel, Flottant et Complexe implantant la signature NOMBRE.

   
   # module Rationnel:NOMBRE =
     struct
      type a = int*int
      type t = { p:int; q:int }
      let create (p0,q0) = { p=p0; q=q0 }
      let add r1 r2 = { p = r1.p*r2.q + r2.p*r1.q; q = r1.q*r2.q }
      let string_of r = (string_of_int r.p)^"/"^(string_of_int r.q)
     end ;;
   module Rationnel : NOMBRE
   
   # module Flottant:NOMBRE =
     struct
      type a = float
      type t = a
      let create x = x
      let add = (+.)
      let string_of = string_of_float
     end ;;
   module Flottant : NOMBRE
   
   # module Complexe:NOMBRE =
     struct
      type a = float*float
      type t = { r:float; i:float }
      let create (r0, i0) = { r=r0; i=i0 }
      let add c1 c2 = { r = c1.r+.c2.r; i = c1.i+.c2.i }
      let string_of c = 
       (string_of_float c.r)^"+"^(string_of_float c.r)^"*i"
     end ;;
   module Complexe : NOMBRE
   
   
   

   
   
   
4. Utiliser ces structures pour définir, par application du foncteur FVecteur, trois modules pour les rationnels, les réels et les complexes.

   
   # module RatVect:VECTEUR = FVecteur(Rationnel) ;;
   module RatVect : VECTEUR
   # module FloVect:VECTEUR = FVecteur(Flottant) ;;
   module FloVect : VECTEUR
   # module ComVect:VECTEUR = FVecteur(Complexe) ;;
   module ComVect : VECTEUR
   
   
   

Arbres lexicaux

1. Définir la signature MOT contenant la déclaration d'un type abstrait alpha pour l'alphabet et t pour les mots sur cet alphabet. On déclarera le mot vide, l'opération de conversion d'un élément de l'alphabet en un mot, l'accès à un élément d'un mot, l'extraction d'un sous-mot, la longueur d'un mot et la concaténation de deux mots.

   
   # module type MOT =
     sig
      type alpha
      type t
      val null : t
      val of_alpha : alpha -> t
      val get : t -> int -> alpha
      val sub : t -> int -> int -> t
      val length : t -> int
      val concat : t -> t -> t
     end ;;
   module type MOT =
     sig
       type alpha
       and t
       val null : t
       val of_alpha : alpha -> t
       val get : t -> int -> alpha
       val sub : t -> int -> int -> t
       val length : t -> int
       val concat : t -> t -> t
     end
   
   
   

   
   
   
2. Définir le foncteur ArbLex, paramétré par un module de signature MOT, qui redéfinit (en fonction des types et opérations sur les mots) le type des arbres lexicaux et les fonctions existe, ajoute et selecte de l'exercice du chapitre 2, page ??.

   
   # module ArbLex (M:MOT) =
      struct
        type node = Lettre of M.alpha * bool * t
        and t = node list
    
        let rec existe m d = 
          let  aux sm i n = 
            match d with
                [] -> false
              | (Lettre (a,b,l))::q when a = M.get sm i -> 
                  if n = 1 then b else existe (M.sub sm (i+1) (n-1)) l       
              | (Lettre (a,b,l))::q when a = M.get sm i -> 
                  existe sm q
        in aux m 0 (M.length m)
    
        let rec ajoute m d = 
          let aux sm i n = 
            if n = 0 then d 
            else 
              match d with 
                  [] -> 
                    let aux = ajoute (M.sub sm (i+1) (n-1)) [] in
                    [ Lettre (M.get sm i, n = 1, aux) ] 
                | (Lettre(a,b,l))::q when a = M.get sm i ->
                    if n = 1 then (Lettre(a,true,l))::q
                    else Lettre(a,b,ajoute (M.sub sm (i+1) (n-1)) l)::q
                | (Lettre(a,b,l))::q -> (Lettre(a,b,l))::(ajoute sm q)
          in aux m 0 (M.length m)
    
        let rec selecte n d = match d with 
            [] -> []
          | (Lettre(a,b,l))::q when n=1 -> 
              let f (Lettre(a,b,_)) = if b then M.of_alpha a else M.null in 
              List.filter ((<>) M.null) (List.map f d) 
          | (Lettre(a,b,l))::q  -> 
              let r = selecte (n-1) l and r2 = selecte n q in
              let pr = List.map (function s -> M.concat (M.of_alpha a) s) r in
              pr@r2
      end ;;
   Characters 161-409:
   Warning: this pattern-matching is not exhaustive.
   Here is an example of a value that is not matched:
   _::_
   module ArbLex :
     functor(M : MOT) ->
       sig
         type node = | Lettre of M.alpha * bool * t
         and t = node list
         val existe : M.t -> t -> bool
         val ajoute : M.t -> t -> t
         val selecte : int -> t -> M.t list
       end
   
   
   

   
   
   
3. Définir le module Chars qui implante les opérations de la signature MOT avec alpha = char et t = string. En déduire un module CharsDic pour les dictionnaires de chaînes de caractères.

   
   # module Chars =
      struct
        type alpha = char
        type t = string
        let null = ""
        let of_alpha c = String.make 1 c 
        let get s i = 
          try s.[i] 
          with Invalid_argument(_) -> raise (Invalid_argument "Chars.get")
        let sub s i1 i2 =
          try String.sub s i1 i2 
          with Invalid_argument(_) -> raise (Invalid_argument "Chars.sub")
        let length = String.length
        let concat = (^)
      end ;;
   module Chars :
     sig
       type alpha = char
       and t = string
       val null : string
       val of_alpha : char -> string
       val get : string -> int -> char
       val sub : string -> int -> int -> string
       val length : string -> int
       val concat : string -> string -> string
     end
   
   # module CharsDic = ArbLex(Chars) ;;
   module CharsDic :
     sig
       type node = ArbLex(Chars).node = | Lettre of Chars.alpha * bool * t
       and t = node list
       val existe : Chars.t -> t -> bool
       val ajoute : Chars.t -> t -> t
       val selecte : int -> t -> Chars.t list
     end