Polymorphe Set mit polymorphe vergleichen von Funktor-Set

Question

Jane Street Core hat eine sehr handliche 'a Core.Set.Poly.t, die ein polymorpher Satz basierend auf polymorphen Pervasives.compare ist.

Zum Beispiel hat dieses Set eine map Funktion, die 'a -> 'b abbildet. Für den Vergleichsstandard ist der OCaml-Satz funktorbasiert und erzeugt einen monomorphen Satz, map Funktionskarten 'a -> 'a.

Gibt es eine bequeme Möglichkeit, ein solches "Poly" -Set mit nur einer Standardbibliothek zu erstellen oder zu emulieren, ohne eine eigene Implementierung von Grund auf neu zu erstellen?

Answer 1

Die stdlib Set kann nicht polymorph sein, da ihr Typkonstruktor keine Argumente hat. Sie können jedoch map aus beliebiger Menge zu beliebigem Satz mit einem Funktor ausdrücken:

module MapSet (S1:Set.S) (S2:Set.S) = struct 
    let map f a = S1.fold (fun elt set -> S2.add (f elt) set) a S2.empty 
end 

Die Nutzung:

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

module MapSI = MapSet (StringSet) (IntSet) 

# IntSet.elements (MapSI.map String.length (StringSet.of_list ["a"; "zonk"; "blart"]));; 
- : IntSet.elt list = [1; 4; 5] 

Wie Sie sehen können, ist es einfach, aber ausführlich und ‚namey‘.

Eine andere Alternative ist die Verwendung einer ('a, unit) Hashtbl als veränderbare Menge, die polymorphe Gleichheit unter der Haube (mit allen üblichen Nachteilen) verwenden wird. Sie können Ihre eigenen map Betrieb leicht implementieren:

let map_keys f tbl = 
    let new_tbl = Hashtbl.create (Hashtbl.length tbl) in 
    Hashtbl.iter (fun k v -> Hashtbl.replace new_tbl (f k) v) tbl; 
    new_tbl 

bewusst sein, dass Hashtbl nicht der schlimmste Fall garantiert nicht vorsehen, dass Set der Fall ist, oder effiziente Vereinigung/diff/Kreuzung Operationen.

Answer 2

Hier ist ein Proof of Concept, das Marshal und Set aus der Standardbibliothek verwendet. Das Argument ist, dass es nicht von Grund auf neu erstellt wird, da es nur eine dünne Schicht über Set ist.

module PSet = Set.Make(struct type t = bytes let compare = compare end) 

module type POLYSET = sig 
    type 'a t 
    val empty : 'a t 
    val mem : 'a -> 'a t -> bool 
    val add : 'a -> 'a t -> 'a t 
    val fold : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b 
    val map : ('a -> 'b) -> 'a t -> 'b t 
end 

module PolySet : POLYSET = struct 
    type 'a t = PSet.t 
    let wrap x = Marshal.to_bytes x [] 
    let unwrap b = Marshal.from_bytes b 0 
    let empty = PSet.empty 
    let mem elt set = 
     PSet.mem (wrap elt) set 
    let add elt set = 
     PSet.add (wrap elt) set 
    let fold f set init = 
     PSet.fold (fun bytes acc -> f (unwrap bytes) acc) set init 
    let map f set = 
     fold (fun elt bset -> add (f elt) bset) set empty 
end 

Es funktioniert für mich:

# module P = Sm.PolySet;; 
module P = Sm.PolySet 
# let x = P.add 14 (P.add 88 P.empty);; 
val x : int P.t = <abstr> 
# P.mem 14 x;; 
- : bool = true 
# P.mem 15 x;; 
- : bool = false 
# P.mem "abc" x;; 
Error: This expression has type int P.t = int Sm.PolySet.t 
     but an expression was expected of type 
     string P.t = string Sm.PolySet.t 
     Type int is not compatible with type string 
# P.fold (fun x l -> x :: l) x [];; 
- : int list = [88; 14] 
# let y = P.map float_of_int x;; 
val y : float P.t = <abstr> 
# P.fold (fun x l -> x :: l) y [];; 
- : float list = [88.; 14.] 

aktualisieren

Der Fairness halber möchte ich darauf hinweisen, dass die Bequemlichkeit dieser Lösung zu einem Preis kommt. Das Marshal-Modul wird Ihre Set-Elemente für jede Operation kopieren (und durchqueren).