Introduction à OCaml
Foncteurs et réutilisabilité
g progmod Programmation modulaire submod Modules et sous-modules progmod->submod foncteurs Foncteurs et réutilisabilité submod->foncteurs fstclassmod Modules de première classe submod->fstclassmod
Table des matières

Les modules paramétrés ou foncteurs (en anglais functors) sont aux modules ce que les fonctions sont aux valeurs. Il s'agit de modules prenant en paramètre un module et renvoyant un autre module. Le module retourné peut à son tour être un foncteur, tout comme une fonction "à plusieurs arguments" est une fonction prenant un paramètre et retournant une autre fonction.

Les foncteurs permettent d'écrire des modules s'abstrayant des structures de données manipulées, dont la représentation et les fonctions de manipulations sont fournies par un module en paramètre. Il est alors aisément possible d'appliquer un même algorithme à deux structures de données différentes, tant que le module en paramètre fournit les fonctions pour effectuer les opérations de base.

1. Définition d'un foncteur

La syntaxe de définition d'un foncteur est la même que pour un module, avec en plus le paramètre attendu: 

module Id =
  functor (Id2 : type de module) ->
  expression de module

Comme pour les fonctions, une syntaxe plus légère est possible:

module Id  (Id2 : type de module) =
  expression de module

L'expression de module peut également être un foncteur. La syntaxe suivante permet donc de simuler un foncteur à plusieurs arguments: 

module Id  (Id2 : type de module) ...
  (IdN : type de module) =
  expression de module

De la même façon, la déclaration d'un foncteur dans les interfaces et les signatures suit celle de déclaration de module: 

module Id :
  functor (Id2 : type de module) ->
   ...
  functor (IdN : type de module) ->
  signature
module Id  (Id2 : type de module) ...
  (IdN : type de module) :
  signature
2. Application

L'application d'un foncteur se fait en utilisant la syntaxe suivante: 

Foncteur(Param)
Foncteur(Param)(Param2)...

L'application d'un foncteur renvoyant un module, nous pouvons donc définir des modules par application de foncteurs de la façon suivante. Ici nous définissons un module Ord, contenant un type t et une fonction de comparaison compare. Nous passons ce module au foncteur Set.Make, qui permet d'obtenir un module de manipulation d'ensembles d'éléments du type t du module passé en paramètre, en l'occurrence Ord.t, donc ici des ensembles d'entiers. 

# module Ord = struct
  type t = int
  let compare (x:int) (y:int) = Stdlib.compare x y
end;;
module Ord : sig type t = int val compare : int -> int -> int end
# module Int_set = Set.Make(Ord);;
module Int_set :
  sig
    type elt = Ord.t
    type t = Set.Make(Ord).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 disjoint : t -> t -> bool
    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 map : (elt -> elt) -> t -> t
    val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
    val for_all : (elt -> bool) -> t -> bool
    val exists : (elt -> bool) -> t -> bool
    val filter : (elt -> bool) -> t -> t
    val filter_map : (elt -> elt option) -> t -> t
    val partition : (elt -> bool) -> t -> t * t
    val cardinal : t -> int
    val elements : t -> elt list
    val min_elt : t -> elt
    val min_elt_opt : t -> elt option
    val max_elt : t -> elt
    val max_elt_opt : t -> elt option
    val choose : t -> elt
    val choose_opt : t -> elt option
    val split : elt -> t -> t * bool * t
    val find : elt -> t -> elt
    val find_opt : elt -> t -> elt option
    val find_first : (elt -> bool) -> t -> elt
    val find_first_opt : (elt -> bool) -> t -> elt option
    val find_last : (elt -> bool) -> t -> elt
    val find_last_opt : (elt -> bool) -> t -> elt option
    val of_list : elt list -> t
    val to_seq_from : elt -> t -> elt Seq.t
    val to_seq : t -> elt Seq.t
    val to_rev_seq : t -> elt Seq.t
    val add_seq : elt Seq.t -> t -> t
    val of_seq : elt Seq.t -> t
  end
# let set = Int_set.of_list [ 1 ; 2 ; 2 ; 2 ; 3 ; 10 ];;
val set : Int_set.t = <abstr>
# Int_set.elements set;;
- : Int_set.elt list = [1; 2; 3; 10]
3. Exemple

Voyons la définition et l'utilisation de foncteurs au travers d'un exemple. Nous souhaitons modéliser un guichet auquel est associé une file d'attente. La file d'attente sera abstraite, permettant la mise en place de différentes politiques de priorité, de façon transparente pour le code de gestion du guichet.

Nous commençons donc par définir le type de la file d'attente: 

# module type QueueType = sig
  type 'a t
  exception Empty
  val create : unit -> 'a t
  val pop : 'a t -> 'a
  val push : 'a -> 'a t -> unit
end;;
module type QueueType =
  sig
    type 'a t
    exception Empty
    val create : unit -> 'a t
    val pop : 'a t -> 'a
    val push : 'a -> 'a t -> unit
  end

Ensuite, nous définissons notre module de guichet, prenant en paramètre une file d'attente: 

# module Guichet = functor (Q : QueueType) -> struct
  let create = Q.create
  let add = Q.push
  let handle_one f guichet =
    try f (Q.pop guichet)
    with Q.Empty -> ()
  let rec handle_all f guichet =
    match
      try Some (Q.pop guichet)
      with Q.Empty -> None
    with
    | None -> ()
    | Some doc -> f doc; handle_all f guichet
end;;
module Guichet :
  functor (Q : QueueType) ->
    sig
      val create : unit -> 'a Q.t
      val add : 'a -> 'a Q.t -> unit
      val handle_one : ('a -> unit) -> 'a Q.t -> unit
      val handle_all : ('a -> 'b) -> 'a Q.t -> unit
    end

Nous ne pouvons pas encore utiliser notre module, puisqu'il s'agit d'un foncteur: 

# Guichet.create();;
File "_none_", line 1, characters 0-14:
Error: The module Guichet is a functor, it cannot have any components

Nous allons simuler notre guichet en utilisant d'abord une file FIFO. La signature demandée pour le module en paramètre est un sous-ensemble de la signature du module Queue, nous pouvons donc utiliser ce module comme modélisation de la file d'attente. En appliquant ce module à notre foncteur, nous obtenons un guichet "premier arrivé, premier servi": 

# module Guichet_FIFO = Guichet(Queue);;
module Guichet_FIFO :
  sig
    val create : unit -> 'a Queue.t
    val add : 'a -> 'a Queue.t -> unit
    val handle_one : ('a -> unit) -> 'a Queue.t -> unit
    val handle_all : ('a -> 'b) -> 'a Queue.t -> unit
  end
# let fifo = Guichet_FIFO.create ();;
val fifo : '_weak1 Queue.t = <abstr>
# List.iter (fun n -> Guichet_FIFO.add n fifo) [ 1 ; 2 ; 3 ; 4 ; 5 ];;
- : unit = ()
# Guichet_FIFO.handle_all (fun n -> print_int n; print_newline ()) fifo;;
1
2
3
4
5
- : unit = ()

Nous pouvons également modéliser la file d'attente par une pile; dans ce cas, le premier servi est le dernier arrivé: 

# module Guichet_pile = Guichet(Stack);;
module Guichet_pile :
  sig
    val create : unit -> 'a Stack.t
    val add : 'a -> 'a Stack.t -> unit
    val handle_one : ('a -> unit) -> 'a Stack.t -> unit
    val handle_all : ('a -> 'b) -> 'a Stack.t -> unit
  end
# let pile = Guichet_pile.create ();;
val pile : '_weak2 Stack.t = <abstr>
# List.iter (fun n -> Guichet_pile.add n pile) [ 1 ; 2 ; 3 ; 4 ; 5 ];;
- : unit = ()
# Guichet_pile.handle_all (fun n -> print_int n; print_newline ()) pile;;
5
4
3
2
1
- : unit = ()

Nous pouvons même faire un foncteur permettant de construire et tester un module de guichet, car les deux codes de test ci-dessus sont les mêmes: 

# module Test (Q : QueueType) = struct
  module G = Guichet(Q)
  let guichet = G.create ()
  let _ = List.iter (fun n -> G.add n guichet) [ 1 ; 2 ; 3 ; 4 ; 5 ]
  let _ = G.handle_all (fun n -> print_int n; print_newline ()) guichet
end;;
module Test :
  functor (Q : QueueType) ->
    sig
      module G :
        sig
          val create : unit -> 'a Q.t
          val add : 'a -> 'a Q.t -> unit
          val handle_one : ('a -> unit) -> 'a Q.t -> unit
          val handle_all : ('a -> 'b) -> 'a Q.t -> unit
        end
      val guichet : int Q.t
    end
# module Foo = Test(Queue);;
1
2
3
4
5
module Foo :
  sig
    module G :
      sig
        val create : unit -> 'a Queue.t
        val add : 'a -> 'a Queue.t -> unit
        val handle_one : ('a -> unit) -> 'a Queue.t -> unit
        val handle_all : ('a -> 'b) -> 'a Queue.t -> unit
      end
    val guichet : int Queue.t
  end
# module Foo = Test(Stack);;
5
4
3
2
1
module Foo :
  sig
    module G :
      sig
        val create : unit -> 'a Stack.t
        val add : 'a -> 'a Stack.t -> unit
        val handle_one : ('a -> unit) -> 'a Stack.t -> unit
        val handle_all : ('a -> 'b) -> 'a Stack.t -> unit
      end
    val guichet : int Stack.t
  end

On remarque que le compilateur impose correctement que les fonctions passées en paramètres aux fonctions handle_one et handle_all prennent en paramètres des valeurs du type des valeurs de la file d'attente: 

# Guichet_FIFO.handle_one print_string fifo;;
File "_none_", line 1, characters 37-41:
Error: This expression has type int Queue.t
       but an expression was expected of type string Queue.t
       Type int is not compatible with type string

On aurait pu masquer la représentation interne du guichet en utilisant une signature et en ajoutant un type de guichet: 

# module type GuichetAbstType = sig
  type 'a t
  val create : unit -> 'a t
  val add : 'a -> 'a t -> unit
  val handle_one : ('a -> unit) -> 'a t -> unit
  val handle_all : ('a -> 'b) -> 'a t -> unit
end;;
module type GuichetAbstType =
  sig
    type 'a t
    val create : unit -> 'a t
    val add : 'a -> 'a t -> unit
    val handle_one : ('a -> unit) -> 'a t -> unit
    val handle_all : ('a -> 'b) -> 'a t -> unit
  end
# module GuichetAbst (Q : QueueType) : GuichetAbstType = struct
  type 'a t = 'a Q.t
  include Guichet(Q)
end;;
module GuichetAbst : functor (Q : QueueType) -> GuichetAbstType
# module Foo=GuichetAbst(Stack);;
module Foo :
  sig
    type 'a t = 'a GuichetAbst(Stack).t
    val create : unit -> 'a t
    val add : 'a -> 'a t -> unit
    val handle_one : ('a -> unit) -> 'a t -> unit
    val handle_all : ('a -> 'b) -> 'a t -> unit
  end

On ne peut plus maintenant accéder à la représentation de la file depuis l'extérieur de la modélisation du guichet: 

# Stack.pop (Foo.create ());;
File "_none_", line 1, characters 10-25:
Error: This expression has type 'a Foo.t = 'a GuichetAbst(Stack).t
       but an expression was expected of type 'b Stack.t
4. Modules anonymes

Il est possible de construire des modules anonymes (sans nom). C'est souvent le cas lors de l'application d'un foncteur prenant un petit module en paramètre. Dans ce cas, on utilise directement la syntaxe struct ... end plutôt que la syntaxe module M = ... et l'utilisation de M dans la suite: 

module Int_set =
  Set.Make (struct type t = int let compare = Stdlib.compare end);;
5. Foncteurs génératifs
OCaml ≥ 4.02.0

Les foncteurs en OCaml sont dits applicatifs, c'est-à-dire qu'appliquer deux fois le même foncteur au même paramètre retournera deux modules dont les types sont identiques. Dans l'exemple ci-dessous, nous créons deux modules M1 et M2 en appliquant le même foncteur au même module en paramètre. Bien que la signature du module résultat indique que le type t est abstrait, M1.t et M2.t sont identiques: nous pouvons utiliser M2.compare pour comparer les deux valeurs créées avec M1.create(). 

# module type I = sig
  type t
  val create : unit -> t
  val compare : t -> t -> int
end;;
module type I =
  sig type t val create : unit -> t val compare : t -> t -> int end
# module F (P: I) : I = struct
  type t = P.t
  let create = P.create
  let compare = P.compare
end;;
module F : functor (P : I) -> I
# module Int : I = struct
  type t = int
  let create () = 12
  let compare = Stdlib.compare
end;;
module Int : I
# module M1 = F(Int);;
module M1 :
  sig
    type t = F(Int).t
    val create : unit -> t
    val compare : t -> t -> int
  end
# module M2 = F(Int);;
module M2 :
  sig
    type t = F(Int).t
    val create : unit -> t
    val compare : t -> t -> int
  end
# let v1 = M1.create();;
val v1 : M1.t = <abstr>
# let v2 = M1.create();;
val v2 : M1.t = <abstr>
# M2.compare v1 v2 ;;
- : int = 0

Il est possible de créer des foncteurs dits génératifs, c'est-à-dire qui créent de nouveaux types lorsqu'ils sont appliqués. Ces foncteurs prennent un argument () en paramètre. En reprenant l'exemple ci-dessus, nous créons un nouveau foncteur F2 prenant aussi () en paramètre. 

# module F2 (P:I) () : I = struct
  type t = P.t
  let create = P.create
  let compare = P.compare
end;;
module F2 : functor (P : I) () -> I
# module M1 = F2(Int) ();;
module M1 : I
# module M2 = F2(Int) ();;
module M2 : I

Les nouveaux modules M1 et M2, construits en appliquant F2 à Int et () ont maintenant des types t incompatibles: 

# let v1 = M1.create();;
val v1 : M1.t = <abstr>
# let v2 = M1.create();;
val v2 : M1.t = <abstr>
# M2.compare v1 v2 ;;
File "_none_", line 1, characters 11-13:
Error: This expression has type M1.t but an expression was expected of type
         M2.t

Ce type de foncteur est utile notamment lorsqu'on souhaite utiliser une même structure de données à base d'indices ou de clés mais qu'on veut que le typage nous garantisse que l'on n'utilise pas une clé d'une structure de données pour une autre structure.

OCaml ≥ 4.02.0