Précédent Index Suivant

Exercices

Listes d'association

Voici un premier petit exercice simple dans lequel il vous est demandé d'implanter un type abstrait polymorphe : les listes d'association. Et d'en donner deux vues différentes.

  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

On illustre, dans ce deuxième exercice, comment les modules paramétrés permettent la généricité et la réutilisation de code en définissant un foncteur de manipulation de vecteurs que l'on pourra instancier selon plusieurs types de nombres.

On se donne la signature suivante :

# 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

Cet exercice reprend les arbres lexicaux vus au chapitre 2, page ??, pour obtenir un module générique de gestion des arbres lexicaux paramétrés par un type abstrait pour les mots.

  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

Précédent Index Suivant