Exercises
Classes and Modules for Data Structures
We wish to construct class hierarchies based on the application of
functors for classical data structures.
We define the following structures
# 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 ;;
-
Write a module with 2 parameters
M1 and M2 of types ELEMENT and STRUCTURE,
constructing a sub-class of ['a] structure in which
'a is constrained to 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
- Write a simple module Integer
which respects the 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
- Write a simple moduleStack
which respects the signature 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
- Apply the functor to its two parameters.
# 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
- Modify the functor by adding the methods
to_string and 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
- Apply the functor again , and then apply it
to the result .
# 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
Abstract Types
Continuing from the previous exercise, we wish to implement a module
with signature ELEMENT of which the class element
uses one instance variable of abstract type.
We define the following parameterized type:
# type 'a t = {mutable x : 'a t; f : 'a t -> unit};;
-
Write the functions apply,
from_string and to_string.
These last two functions will use the Marshal module.
# 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>
- Write a signature S which corresponds
to the signature previously inferred by abstracting the 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
- Write a functor which takes a parameter
with signature S and returns a module of which the signature
is compatible with 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
- Use the resulting module as the parameter of
the module from the previous exercise.
# 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