Cours 6

Htmligure
Version & licenses
Creative Commons License

Étendre des modules

Guyslain
Thursday, 21 July 2016

Retour au sommaire.

Étendre un module.

Un des cas d'usage des modules est de pouvoir définir une implémentation minimaliste d'une interface, puis de l'appliquer à un foncteur pour dériver automatiquement de nombreuses fonctions.

Les files de priorités.

Continuons sur l'exemple des files de priorités. On pourrait à partir de cette file de priorité définir automatiquement des fonctions pour créer une file de priorité depuis une liste, ou extraire une liste triée depuis une file de priorité. Cela correspondrait à enrichir l'interface des modules de priorité pour obtenir ceci :

  1. module type Heap = sig
  2. include MinimalHeap
  3. val of_list : key list -> t
  4. val to_list : t -> key list
  5. val sort : key list -> key list
  6. end

On note ici l'utilisation du mot-clé include qui permet d'inclure dans une interface le contenu d'une autre interface. En plus des définitions de la file de priorité minimale, nous trouvons donc les fonctions de conversions de/vers les listes et une fonction de tri.

Il n'est alors pas nécessaire de redéfinir entièrement le module de files de priorité : on peut réutiliser l'implémentation des tas gauches, à l'aide d'un foncteur.

  1. module Extend :
  2. functor (Heap : MinimalHeap) ->
  3. Heap with type t = Heap.t and type key = Heap.key
  4. = functor (Heap : MinimalHeap) ->
  5. struct
  6. include Heap

  8. let of_list list =
  9. List.fold_left (fun heap elt -> insert elt heap) empty list

  11. let to_list heap =
  12. let rec accumulate sorted heap =
  13. match observe heap with
  14. | None -> List.rec sorted
  15. | Some (top,popped) -> accumulate (top :: sorted) popped
  16. in
  17. accumulate [] heap

  19. let sort list = list |> of_list |> to_list
  20. end

À nouveau, dans l'implémentation, include permet de récupérer toutes les définitions d'un module. On peut noter qu'il faut correctement exporter les deux types t et key. Dans ce foncteur, l'argument Heap peut être n'importe quel module implémentant l'interface MinimalHeap, ce qui a deux conséquences :

  • ce n'est pas nécessairement l'implémentation par tas gauche, on n'a donc pas accès à la structure privée du module Heap.
  • ce n'est pas nécessairement l'implémentation par tas gauche, donc n'importe quelle implémentation minimale de files de priorité peut être étendue par le foncteur Extend. Nous avons codé une fois pour toute les fonctions d'Extend.

Un exemple d'utilisation de cette technique est la librairie Ocamlgraph d'algorithmes sur les graphes. Tous les algorithmes sont écrits dans des foncteurs, prenant un module d'interface Graph (en fait, il y a même plusieurs interfaces possibles pour les graphes). Chaque algorithme est donc implémenté une fois, définitivement, et peut être ensuite utilisé avec n'importe quelle implémentation de graphes, ce qui permet d'utiliser des représentations très haut-niveau de graphes, selon les besoins de l'utilisateur de la librairie. Des implémentations par défaut sont aussi proposées.

Les monades.

Étudions un autre exemple. Rappelons l'interface des monades :

  1. module type Monad = sig
  2. type 'a t
  3. val return : 'value -> 'value t
  4. val (>>=) : 'value t -> ('value -> 'result t) -> 'result t
  5. end

L'un des intérêts des monades est de modéliser le séquencement d'actions : faire une chose, puis une autre, puis une autre. Nous avons vu à travers de nombreux exemples que le (>>=) s'utilise de la même façon que le pipe (|>), mais avec des fonctions produisant des résultats dans le type paramétré de la monade.

Une fois les deux opérations return et (>>=) définies, il est possible d'en définir plein d'autres automatiquement. On peut donc définir un foncteur (avec une petite sélection de fonctions possibles) :

  1. module type ExtMonad = sig
  2. include Monad

  4. (** Monads are functors *)
  5. val map : 'value t -> ('value -> 'result) -> 'result t

  7. (** [join] = [flatten] = [concat] *)
  8. val join : 'value t t -> 'value t

  10. (** applies actions of a sequence and return the sequence of results *)
  11. val sequence : 'result t list -> 'result list t

  13. (** [fold] when the action on each element is monadic *)
  14. val foldM : ('state -> 'elt -> 'state t) -> 'state -> 'elt list -> 'state t

  16. (** Lifts an ordinary function to a "monadic" function. *)
  17. val lift : ('arg -> 'result) -> ('arg -> 'result t)
  18. end

  20. module ExtendMonad :
  21. functor (M : Monad) -> ExtMonad with type 'a t = 'a Monad.t
  22. = functor (M : Monad) ->
  23. struct
  24. include M

  26. let map fct ma = ma >>= fun a -> return (fct a)

  28. let join mma = mma >>= fun ma -> ma

  30. let sequence actions =
  31. let rec accumulate results = function
  32. | [] -> return (List.rev results)
  33. | first :: actions ->
  34. first >>= fun first_res ->
  35. accumulate (first_res :: results) actions
  36. in
  37. accumulate [] actions

  39. let foldM fct init args =
  40. List.fold_left
  41. (fun ma elt -> ma >>= fun a -> fct a elt)
  42. (return init)
  43. args

  45. let lift fct arg = return (fct arg)
  46. end

Retour au sommaire.