다형성이있는 Functor 기반의 집합으로 구성된 집합

Question

Jane Street Core는 다형성 Pervasives.compare을 기반으로하는 다형성 집합 인 매우 편리한 'a Core.Set.Poly.t을가집니다.

예를 들어,이 세트는 을 매핑하는 map 함수가 있습니다. 비교 표준 OCaml 세트는 펑터 기반이며, map 함수 맵 'a -> 'a 인 단일 형태 집합을 생성합니다.

표준 라이브러리 만 사용하여 이러한 "폴리"세트를 생성하거나 에뮬레이트하는 편리한 방법이 있습니까? 처음부터 자신의 구현을 롤아웃하지 않아도됩니까?

Answer 1

형식 생성자에 인수가 없으므로 stdlib Set은 다형성 일 수 없습니다. 그러나 펑터으로 임의의 집합에 임의의 세트에서 map을 표현할 수 :

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 

사용법 : 당신이 볼 수 있듯이

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] 

, 그것은 간단하지만, 자세한와 'namey'입니다.

또 다른 대안은 변경 가능한 집합으로 ('a, unit) Hashtbl을 사용하는 것입니다.이 집합은 후드에서 다형성 평등을 사용합니다 (모든 일반적인 단점이 있음).

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 

가 Hashtbl은 최악의 경우는 Set가하는, 또는 효율적인 조합/DIFF/교차로 운영 보장 제공하지 않는 것을 염두해야합니다 : 당신은 쉽게 자신의 map 작업을 구현할 수 있습니다.

Answer 2

다음은 표준 라이브러리의 마샬링 및 집합을 사용하는 개념 증명입니다. 인자는 Set의 맨 위에있는 얇은 레이어이기 때문에 처음부터 빌드 된 것이 아닙니다.

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 

그것은 나를 위해 작동 :이 솔루션의 편의를 비용으로 오는 것을 지적한다 공정성에

# 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.] 

업데이트

. Marshal 모듈은 각 작업에 대해 설정된 요소를 복사 (및 추적)합니다.