Set

Le Module Set

Pour faire une structure de donnée de type ensemble ("set" en anglais) :

# module SS = Set.Make(String);;
module SS :
  sig
    type elt = String.t
    type t = Set.Make(String).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

Ici il s'agit d'un ensemble de chaîne de caractère (string en anglais).

Pour créer un ensemble vous pouvez commencer par un ensemble vide auquel vous pourrez ajouter des éléments par la suite :

# let s = SS.empty;;
val s : SS.t = <abstr>

Ou vous pouvez créer un ensemble contenant un élément en fournissant cet élément ce cette façon :

# let s = SS.singleton "hello";;
val s : SS.t = <abstr>

Puis ajouter une série d'éléments à un ensemble peut se faire comme ceci :

# let s =
    List.fold_right SS.add ["bonjour"; "le"; "monde"; "communaute"; "gestionaire";
                            "truc"; "bleu"; "vert"] s;;
val s : SS.t = <abstr>

Maintenant pour pouvoir nous amuser avec nos ensembles nous allons vraissemblablement vouloir regarder ce qu'ils contiennent. Pour ce faire nous allons écrire une fonction qui affiche le contenu d'un ensemble :

# (* Afficher un retours à la ligne "\n" apres l'affichage de chaque ligne *)
  let print_set s = 
    SS.iter print_endline s;;
val print_set : SS.t -> unit = <fun>

Si nous souhaitons enlever un élément en particulier d'un ensemble il y a la fonction remove. Cependant si nous souhaitons enlever plusieurs éléments spécifiques en une passe nous pouvons utiliser un filtre ("filter" en anglais). Voici comment filtrer tous les mots constitués de plus de 5 caractères :

# let my_filter str =
    String.length str <= 5;;
val my_filter : string -> bool = <fun>
# let s2 = SS.filter my_filter s;;
val s2 : SS.t = <abstr>

ou en utilisant une fonction anonyme :

# let s2 = SS.filter (fun str -> String.length str <= 5) s;;
val s2 : SS.t = <abstr>

Pour vérifier si un élément est déjà présent dans un ensemble nous pouvons faire :

# SS.mem "bonjour" s2;;
- : bool = false

Le module Set fournit également les fonctions correspondant aux opérations théoriques : union, intersection et différence. Par exemple la différence entre l'ensemble original et l'ensemble de mots courts (≤ 5 caractères) est un ensemble de mots longs :

# print_set (SS.diff s s2);;
bonjour
communaute
gestionaire
- : unit = ()

Notez que le module Set fournit une structure de donnée fonctionnelle pure, ce qui veut dire que supprimer un élément n'altère en aucune façon l'ensemble original mais à la place renvoie un nouvel ensemble très proche de celui de départ (et qui partage la plupart de sa structure interne).