module SceneSet = Set.Make (struct type t = int * int let compare (x1, y1) (x2, y2) = if x1 < x2 then -1 else if x1 > x2 then 1 else y2 - y1 end);;
Le foncteur Set.Make
sert à construire
un module manipulant efficacement des ensembles d'éléments d'un type
(passé en paramètre). Il prend en argument un module de signature
sig type t val compare : t -> t -> int end
La fonction compare
prend deux arguments
x et y et retourne un résultat strictement
négatif si x < y, nul si x ≡ y, et strictement
positif si x > y,
pour une relation de (pré)ordre total ≤. L'ordre choisi importe
peu ; cependant, Set.Make
considèrera
que deux éléments x et y sont identiques si
compare x y
=0.
Ici, j'ai choisi de donner explicitement l'ordre lexicographique
sur les couples d'entiers. J'aurais pu me contenter d'écrire
let compare = Pervasives.compare
:
la fonction
Pervasives.compare : 'a -> 'a -> int
est définie polymorphiquement sur tous les types Caml (sauf les types
fonctionnels) et les munit chacun d'un ordre total.
On obtient un module présentant la signature suivante :
module SceneSet : sig type elt = int * int and 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 for_all : (elt -> bool) -> t -> bool val exists : (elt -> bool) -> t -> bool val filter : (elt -> bool) -> t -> t val partition : (elt -> bool) -> t -> t * t val cardinal : t -> int val elements : t -> elt list val min_elt : t -> elt val max_elt : t -> elt val choose : t -> elt end
SceneSet.t
est le type des ensembles de
paires d'entiers, SceneSet.empty
est
l'ensemble vide, et on a les opérations d'union, d'intersection, etc.
Voir la documentation.