OCaml: imposta i moduli

Question

Desidero utilizzare OCaml per generare insiemi di dati ed effettuare confronti tra loro. Ho visto la documentazione per i tipi di modulo come Set.OrderType, Set.Make, ecc., Ma non riesco a capire come inizializzare un set o in altro modo usarli.

Answer 1

I set sono definiti utilizzando un'interfaccia funzionale. Per ogni tipo di dato, devi creare un modulo Set per quel tipo usando il functor Set.Make. Uno sventurato svista delle librerie standard è che non definiscono le istanze Set per i tipi predefiniti. Nei casi più semplici, è sufficiente utilizzare Pervasives.compare. Ecco una definizione che lavora per int:

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

Il modulo IntSet sarà implementare l'interfaccia Set.S. Ora è possibile operare sul set usando il modulo di IntSet:

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

Si noti che non c'è bisogno di definire in modo esplicito la struttura di ingresso per Set.Make come OrderedType; l'inferenza di tipo farà il lavoro per te. In alternativa, è possibile utilizzare la seguente definizione:

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

module IntSet = Set.Make(IntOrder) 

Questo ha il vantaggio che è possibile ri-utilizzare lo stesso modulo di creare un'istanza di un Map:

module IntMap = Map.Make(IntOrder) 

Si perde un po 'di genericità nell'utilizzo funtori, perché il tipo degli elementi è fisso. Ad esempio, non sarà possibile definire una funzione che prende uno Set di un tipo arbitrario e esegue alcune operazioni su di esso. (Per fortuna, il modulo Set si dichiara molte operazioni utili su Set s.)

Answer 2

Oltre alla risposta di Chris, può essere utile per dire che alcuni moduli della libreria standard già aderire alla firma OrderedType. Ad esempio, si può semplicemente fare:

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 *) 

E così via.

Ecco un semplice esempio di utilizzo per StringSet; ricorda che gli insiemi sono strutture dati funzionali, quindi aggiungere un nuovo elemento a un set restituisce un nuovo set:

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