Exercices
Classes et modules pour structures de données
On désire construire des hiérarchies de classes à partir de
l'application de foncteurs
pour des structures de données classiques.
On définit les signatures suivantes :
# module type ELEMENT =
sig
class element :
string ->
object
method to_string : unit -> string
method of_string : string -> unit
end
end ;;
# module type STRUCTURE =
sig
class ['a] structure :
object
method add : 'a -> unit
method del : 'a -> unit
method mem : 'a -> bool
method get : unit -> 'a
method all : unit -> 'a list
method iter : ('a -> unit) -> unit
end
end ;;
-
Écrire un module à 2 paramètres
M1 et M2 de types ELEMENT et STRUCTURE,
construisant une sous-classe de ['a] structure dont le
'a est contraint à M1.element.
# module Struct_Elmt (E:ELEMENT) (S:STRUCTURE) =
struct
class e_structure =
object
inherit [E.element] S.structure
end
end ;;
module Struct_Elmt :
functor(E : ELEMENT) ->
functor(S : STRUCTURE) ->
sig
class e_structure :
object
method add : E.element -> unit
method all : unit -> E.element list
method del : E.element -> unit
method get : unit -> E.element
method iter : (E.element -> unit) -> unit
method mem : E.element -> bool
end
end
- Écrire un module simple Entier
respectant la signature ELEMENT.
# module Entier : ELEMENT =
struct
class element v =
object
val mutable n = int_of_string v
method to_string () = string_of_int n
method of_string x = n <- (int_of_string x)
end
end ;;
module Entier : ELEMENT
- Écrire un module simple Pile
respectant la signature de STRUCTURE.
# module Pile : STRUCTURE =
struct
class ['a] structure =
object
val mutable p = ( [] : 'a list )
method add x = p <- x::p
method del x = p <- List.filter ((<>) x) p
method mem x = List.mem x p
method get () = List.hd p
method all () = p
method iter f = List.iter f p
end
end ;;
module Pile : STRUCTURE
- Appliquer le foncteur à ces deux
paramètres.
# module Pile_Entier = Struct_Elmt(Entier)(Pile) ;;
module Pile_Entier :
sig
class e_structure :
object
method add : Entier.element -> unit
method all : unit -> Entier.element list
method del : Entier.element -> unit
method get : unit -> Entier.element
method iter : (Entier.element -> unit) -> unit
method mem : Entier.element -> bool
end
end
- Modifier le foncteur initial en ajoutant
les méthodes to_string et of_string.
# let split c s =
let suffix s i =
try String.sub s i ((String.length s)-i)
with Invalid_argument("String.sub") -> ""
in
let rec split_from n =
try let p = String.index_from s n c
in (String.sub s n (p-n)) :: (split_from (p+1))
with Not_found -> [ suffix s n ]
in
if s="" then [] else split_from 0 ;;
val split : char -> string -> string list = <fun>
# module Elmt_Struct (E:ELEMENT) (S:STRUCTURE) =
struct
class element v =
object (self)
val n = new S.structure
method to_string () =
let res = ref "" in
let f x = res := !res ^ ((x#to_string ()) ^ " ") in
n#iter f ;
!res
method of_string x =
let l = split ' ' x in
List.iter (fun x -> n#add (new E.element x)) l
initializer self#of_string v
end
end ;;
module Elmt_Struct :
functor(E : ELEMENT) ->
functor(S : STRUCTURE) ->
sig
class element :
string ->
object
val n : E.element S.structure
method of_string : string -> unit
method to_string : unit -> string
end
end
- Appliquer le foncteur de nouveau, puis
l'appliquer au résultat.
# module Entier_Pile = Elmt_Struct (Entier) (Pile) ;;
module Entier_Pile :
sig
class element :
string ->
object
val n : Entier.element Pile.structure
method of_string : string -> unit
method to_string : unit -> string
end
end
# module Entier_Pile_Pile = Elmt_Struct (Entier_Pile) (Pile) ;;
module Entier_Pile_Pile :
sig
class element :
string ->
object
val n : Entier_Pile.element Pile.structure
method of_string : string -> unit
method to_string : unit -> string
end
end
Types abstraits
En reprenant l'exercice précédent, on cherche à implanter un module de signature
ELEMENT dont la classe element utilise une variable d'instance
d'un type abstrait.
On définit le type paramétré suivant :
# type 'a t = {mutable x : 'a t; f : 'a t -> unit};;
-
Écrire les fonctions apply,
from_string et to_string. Ces deux dernières
fonctions utilisent le module Marshal.
# let apply val_abs = val_abs.f val_abs.x ;;
val apply : 'a t -> unit = <fun>
# let from_string s = Marshal.from_string s 0 ;;
val from_string : string -> 'a = <fun>
# let to_string v = Marshal.to_string v [Marshal.Closures] ;;
val to_string : 'a -> string = <fun>
- Écrire une signature S correspondant
à la signature inférée précédemment en abstrayant le type t.
# module type S =
sig
type t
val apply : t -> unit
val from_string : string -> t
val to_string : t -> string
end ;;
module type S =
sig
type t
val apply : t -> unit
val from_string : string -> t
val to_string : t -> string
end
- Écrire un foncteur qui prend un paramètre
de signature S et retourne un module dont la signature est
compatible avec ELEMENT.
# module Element_of (M:S) =
struct
class element v =
object
val mutable n = M.from_string v
method to_string () = M.to_string n
method of_string x = n <- M.from_string x
end
end ;;
module Element_of :
functor(M : S) ->
sig
class element :
string ->
object
val mutable n : M.t
method of_string : string -> unit
method to_string : unit -> string
end
end
- Utiliser le module résultat comme paramètre
du module de l'exercice précédent.
# module Abstrait_Pile (M:S) = Elmt_Struct (Element_of(M)) ;;
module Abstrait_Pile :
functor(M : S) ->
functor(S : STRUCTURE) ->
sig
class element :
string ->
object
val n : Element_of(M).element S.structure
method of_string : string -> unit
method to_string : unit -> string
end
end