Modules paramétrés

Modules paramétrés

Les modules paramétrés sont aux modules ce que les fonctions sont aux valeurs. Tout comme une fonction construit une nouvelle valeur à partir de valeurs paramètres, un module paramétré permet de construire un nouveau module à partir de modules déjà construits. On donne également le nom de foncteurs aux modules paramétrés.

L'introduction des foncteurs dans le langage des modules permet d'accroître les possibilités de réutilisation du code défini dans les structures.

Un foncteur se définit avec une syntaxe fonctionnelle :

Syntaxe

functor ( Nom : signature ) -> structure

# module Couple = functor ( Q : sig type t end ) -> 
   struct type couple = Q.t * Q.t end ;;
module Couple :
  functor(Q : sig type t end) -> sig type couple = Q.t * Q.t end

Comme pour les fonctions, il existe un raccourci syntaxique à la déclaration de foncteurs :

Syntaxe

module Nom₁ ( Nom₂ : signature ) = structure


# module Couple ( Q : sig type t end ) =  struct type couple = Q.t * Q.t end ;;
module Couple :
  functor(Q : sig type t end) -> sig type couple = Q.t * Q.t end

Un foncteur peut admettre plusieurs paramètres.

Syntaxe

functor ( Nom₁ : signature₁ ) -> :

functor ( Nom_n : signature_n ) -> structure

On peut, ici également, utiliser le raccourci syntaxique :

Syntaxe

module Nom (Nom₁ : signature₁ ) ...( Nom_n : signature_n ) =

structure

L'application d'un foncteur à ses paramètres se fait selon le schéma syntaxique suivant :

Syntaxe

module Nom = foncteur ( structure₁ ) ...( structure_n )

Notez que chaque paramètre est inscrit entre parenthèses. Le résultat de l'application peut être un module simple ou, à nouveau un foncteur, selon le nombre de paramètres réclamés par le foncteur.

Warning

Il n'est pas possible de créer une signature par application d'une signature << fonctorielle >> à d'autres signatures.

Un foncteur qui explicite complètement sa communication avec d'autres modules, c'est-à-dire qui ne fait pas référence directement à un élément d'un autre module hormis ses paramètres, est facilement réutilisable. On peut effectivement l'appliquer à différents arguments selon le cadre de son emploi. Il y a un parallèle entre une fonction complètement paramétrée (sans variable libre) et un foncteur complètement paramétré.

Foncteurs et réutilisabilité

La distribution d'Objective CAML fournit trois modules définissant des foncteurs. Deux d'entre eux prennent comme argument un module fournissant un type de données totalement ordonné; c'est-à-dire respectant la signature suivante :

# module type OrderedType =
   sig
     type t
     val compare: t -> t -> int
   end ;;
module type OrderedType = sig type t val compare : t -> t -> int end

La fonction compare prend deux arguments et rend une valeur négative si le premier est inférieur au second, une valeur nulle s'ils sont égaux, et une valeur positive si le premier est supérieur au second. Voici un exemple de type ordonné.

# module OrderedIntPair = 
   struct  
     type t = int * int 
     let compare (x1,x2) (y1,y2) = let q = x1-y1 in if q=0 then x2-y2 else q 
   end ;;
module OrderedIntPair :
  sig type t = int * int val compare : int * int -> int * int -> int end

Le foncteur Make du module Map construit un module qui implante des tables d'association ayant pour clés des valeurs du type ordonné passé en argument. Ce module fournit des services comparables à ceux des listes d'associations du module List mais en utilisant une structure de données légèrement plus complexe (des arbres binaires équilibrés).

# module AssocIntPair = Map.Make (OrderedIntPair) ;;
module AssocIntPair :
  sig
    type key = OrderedIntPair.t
    and 'a t = 'a Map.Make(OrderedIntPair).t
    val empty : 'a t
    val add : key -> 'a -> 'a t -> 'a t
    val find : key -> 'a t -> 'a
    val remove : key -> 'a t -> 'a t
    val mem : key -> 'a t -> bool
    val iter : (key -> 'a -> unit) -> 'a t -> unit
    val map : ('a -> 'b) -> 'a t -> 'b t
    val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
  end

Le foncteur Make permet de construire des tables d'associations ayant pour clé n'importe quel type de données dont on saura écrire une fonction compare.

Le module Set fournit lui aussi un foncteur Make prenant en argument un type ordonné et construisant un module implantant les ensembles de valeurs de ce type.


# module SetIntPair = Set.Make (OrderedIntPair) ;;
module SetIntPair :
  sig
    type elt = OrderedIntPair.t
    and t = Set.Make(OrderedIntPair).t
    val empty : t
    val is_empty : t -> bool
    val mem : elt -> t -> bool
    val add : elt -> t -> t
    val singleton : elt -> t
    val remove : elt -> t -> t
    val union : t -> t -> t
    val inter : t -> t -> t
    val diff : t -> t -> t
    val compare : t -> t -> int
    val equal : t -> t -> bool
    val subset : t -> t -> bool
    val iter : (elt -> unit) -> t -> unit
    val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
    val cardinal : t -> int
    val elements : t -> elt list
    val min_elt : t -> elt
    val max_elt : t -> elt
    val choose : t -> elt
  end

Nous avons avec SetIntPair.t un type pour les ensembles de couples d'entiers avec toutes les fonctions classiques sur les ensembles. L'illustration de la réutilisabilité nous est donné en construisant les ensembles d'ensembles de paires d'entiers.


# module SetofSet = Set.Make (SetIntPair) ;;

# let x = SetIntPair.singleton (1,2) ;;           (* x = { (1,2) }        *)
val x : SetIntPair.t = <abstr>
# let y = SetofSet.singleton SetIntPair.empty ;;  (* y = { {} }           *)
val y : SetofSet.t = <abstr>
# let z = SetofSet.add x y ;;                     (* z = { {(1,2)} ; {} } *)
val z : SetofSet.t = <abstr>

Le foncteur Make du module Hashtbl fonctionne de manière similaire à celui du module Map mais en construisant des tables de hachage à la place d'arbres équilibrés. L'argument de ce foncteur est un peu différent; outre le type des clés de la table de hachage, il doit fournir simplement une fonction testant l'égalité entre deux clés à la place d'une fonction de comparaison. De plus, il est nécessaire de donner la fonction de hachage, c'est-à-dire une fonction associant un entier à une clé.

# module type HashedType =
   sig
     type t
     val equal: t -> t -> bool
     val hash: t -> int
   end ;;
module type HashedType =
  sig type t val equal : t -> t -> bool val hash : t -> int end
# module IntMod13 = 
   struct 
     type t = int 
     let equal = (=) 
     let hash x = x mod 13 
   end ;;
module IntMod13 :
  sig type t = int val equal : 'a -> 'a -> bool val hash : int -> int end
# module TblInt = Hashtbl.Make (IntMod13) ;;
module TblInt :
  sig
    type key = IntMod13.t
    and 'a t = 'a Hashtbl.Make(IntMod13).t
    val create : int -> 'a t
    val clear : 'a t -> unit
    val add : 'a t -> key -> 'a -> unit
    val remove : 'a t -> key -> unit
    val find : 'a t -> key -> 'a
    val find_all : 'a t -> key -> 'a list
    val mem : 'a t -> key -> bool
    val iter : (key -> 'a -> unit) -> 'a t -> unit
  end

Déclarations locales de modules

Parmi les extensions du langage, il existe la possibilité de déclarer localement un module.

Syntaxe

let module Nom = structure

in expr

Par exemple, nous souhaitons utiliser le module Set pour écrire une fonction de tri sur les listes d'entiers en insérant chaque élément de la liste dans un ensemble et en récupérant à la fin la liste des éléments de l'ensemble obtenu.


# let sort l =
   let module M = 
      struct 
        type t = int  
        let compare = (-) 
      end 
  in
    let module MSet = Set.Make(M) 
    in  MSet.elements (List.fold_right MSet.add l MSet.empty) ;;
val sort : int list -> int list = <fun>

# sort [ 5 ; 3 ; 8 ; 7 ; 2 ; 6 ; 1 ; 4 ] ;; 
- : int list = [1; 2; 3; 4; 5; 6; 7; 8]

Objective CAML ne permet pas de faire sortir d'un module local une valeur ayant un type qui n'est pas connu à l'extérieur de l'expression.


# let test = 
   let module Foo = 
     struct 
       type t 
       let id x = (x:t)
     end
   in Foo.id ;;
Characters 15-101:
This `let module' expression has type Foo.t -> Foo.t
In this type, the locally bound module name Foo escapes its scope