Le blog de SpiceGuid

Un article de SpiceGuid    Pas de commentaires

S’il y a une chose qui m’étonne c’est qu’avec toutes les abstractions à la disposition du programmeur OCaml il soit encore difficile d’implanter correctement un TAD ensemble.

Dans ma bibliothèque de structures de données (OCaml-Idaho) j’ai opté pour une implantation par arbre de recherche équilibré. La cohérence de mes fonctions de comparaison est assurée par un paramétrage par les modules. Grâce aux higher-order modules on peut associer chaque type à une valeur. En associant le type set à une fonction compare on s’assure qu’il ne sera pas possible de faire l’union de deux ensembles d’éléments de même sorte mais qui n’utiliseraient pas la même fonction de comparaison.

C’est sécurisant et ça me convenait très bien tant que j’implantais des fonctions comme union, intersection, difference, subset ou bien filter.

Là où plus rien ne va c’est avec le produit cartésien de deux ensembles.

Le problème c’est que mon type set est trop monomorphe, il n’est pas paramétré par le type des éléments :

    type item =
      Ord.ordered

    type set =
      node option
    and node =
      {left: set; item: item; right: set}

Or le produit cartésien ne peut pas avoir ce type monomorphe :

    set -> set -> set

Son type est forcément polymorphe :

    product: 'a set -> 'b set -> ('a * 'b) set

Même en présence d’ensembles de même nature son type est encore polymorphe :

    product: 'a set -> 'a set -> ('a * 'a) set

Au contraire, avec un type set polymorphe le produit cartésien est (presque) facilement accessible.
Un nouveau type ensemble polymorphe :

    type 'a set =
      'a node option
    and 'a node =
      {left: 'a set; item: 'a; right: 'a set}

L’union efficace de deux ensembles (en temps proportionnel au cardinal du résultat, voir la source de Ocaml-Idaho ou de Set.Make) :

    let union cmp ta tb =
      ...

flatten_map est une fonction intéressante, son effet est tout à fait comparable à celui de son équivalent pour les listes, chaque noeud est développé en arbre par une fonction f puis l’arbre des arbres est applati en une union de tous les arbres :

    let rec flatten_map cmp f init = function
      | None -> init
      | Some n ->
          union cmp
          (flatten_map cmp f init n.left)
          (flatten_map cmp f (f n.item) n.right)

    let flatten_map cmp f = flatten_map cmp f None

On a aussi un vrai foncteur, qui au lieu d’être de type set -> set est de type ‘a set -> ‘b set :

    let rec map f = function
      | None -> None  
      | Some n -> Some
          {left = map f n.left; item = f n.item; right = map f n.right}

Du coup on peut implanter le produit d’un ensemble s par une valeur y :

    let times s y =
      map (fun x -> x,y) s

Et finalement, le produit cartésien d’un ensemble sa par un ensemble sb :

    let product cmp sa sb =
      flatten_map cmp (times sa) sb

Malheureusement on ne peut pas tout avoir, avec un type polymorphe il n’est pas possible d’associer chaque type ‘a set à une valeur de type ‘a -> ‘a -> int.
Il devient alors tout à fait possible de construire des ensembles qui n’ont plus d’ordonné que le nom.

Tout ça pour dire que si OCaml-Idaho n’offre pas le produit cartésien c’est qu’il y a une bonne raison. Une bibliothèque réutilisable doit imposer sa règle d’or, elle ne peut pas faire le pari que ses utilisateurs la connaissent et la suivront à la lettre.
J’espère que ce billet vous aura aidé à comprendre ce choix et à le contourner si le besoin s’en fait sentir.

Pour les accros aux modules

Il est sans doute possible de concevoir un module d’ordre supérieur qui offre le produit cartésien.
L’idée c’est d’embarquer l’opération dans un module dédié, les opérandes de l’opération product devraient alors être construites à partir des sous-modules SetA et SetB :

module Product(OrdA : Ordered)(OrdB : Ordered)
  :
  sig
    module SetA = ...
    module SetB = ...
    module SetAxB = ...
    val product: SetA.set -> SetB.set -> SetAxB.set 
  end
  =
  struct

     module SetA =
     struct
       type item = OrdA.ordered
       type set
     end

     module SetB =
     struct
       type item = OrdB.ordered
       type set
     end

     module SetAxB =
     struct
       type item = OrdA.ordered * OrdB.ordered
       type set
     end

    let product sa sb = ...
    
  end

Malheureusement cette solution semble aussi lourde à implanter (à l’aide d’un type set polymorphe!) que peu flexible à utiliser.