Question OCaml: Set modules


Je veux utiliser OCaml pour générer des ensembles de données et les comparer. J'ai vu la documentation pour les types de modules comme Set.OrderType, Set.Make, etc, mais je ne peux pas comprendre comment initialiser un ensemble ou les utiliser autrement.


16
2017-09-20 22:43


origine


Réponses:


Les ensembles sont définis à l'aide d'une interface functorielle. Pour tout type donné, vous devez créer un Set module pour ce type utilisant le Set.Make foncteur. Il est regrettable que les bibliothèques standard ne définissent pas Set instances pour les types intégrés. Dans la plupart des cas simples, il suffit d'utiliser Pervasives.compare. Voici une définition qui fonctionne pour int:

module IntSet = Set.Make( 
  struct
    let compare = Pervasives.compare
    type t = int
  end )

Le module IntSet mettra en œuvre le Set.S interface. Maintenant, vous pouvez utiliser des ensembles en utilisant le IntSet module:

let s = IntSet.empty ;;
let t = IntSet.add 1 s ;;
let u = IntSet.add 2 s ;;
let tu = IntSet.union t u ;;

Notez que vous n'avez pas besoin de définir explicitement la structure d'entrée pour Set.Make en tant que OrderedType; La déduction de type fera le travail pour vous. Vous pouvez également utiliser la définition suivante:

module IntOrder : Set.OrderedType = struct
  type t = int
  let compare = Pervasives.compare
end

module IntSet = Set.Make( IntOrder )

Cela a l'avantage que vous pouvez réutiliser le même module pour instancier un Map:

module IntMap = Map.Make( IntOrder )

Vous perdez de la généricité en utilisant des foncteurs, car le type des éléments est fixe. Par exemple, vous ne pourrez pas définir une fonction qui prend une Set de quelque type arbitraire et effectue une opération sur elle. (Heureusement, le Set le module lui-même déclare de nombreuses opérations utiles sur Sets.)


28
2017-09-20 23:25



En plus de la réponse de Chris, il peut être utile de dire que certains modules de bibliothèque standard adhèrent déjà à la OrderedType Signature. Par exemple, vous pouvez simplement faire:

module StringSet = Set.Make(String) ;;       (* sets of strings *)
module Int64Set = Set.Make(Int64) ;;         (* sets of int64s *)
module StringSetSet = Set.Make(StringSet) ;; (* sets of sets of strings *)

Etc.

Voici un exemple d'utilisation simple pour StringSet; Rappelez-vous que les ensembles sont des structures de données fonctionnelles. Par conséquent, l'ajout d'un nouvel élément à un ensemble renvoie un nouvel ensemble:

let set = List.fold_right StringSet.add ["foo";"bar";"baz"] StringSet.empty ;;
StringSet.mem "bar" set ;; (* returns true *)
StringSet.mem "zzz" set ;; (* returns false *)

10
2017-09-21 14:35