How to apply functor Set.Make to parametrized modle

Learning
1

I am currently trying to build a set over some type that can be parametrized with another type, eg :

module Test = struct
    type 'a t = 'a another_extern_type
    let compare t1 t2 = Stdlib.Int.compare t1.id t2.id
end

module St = Set.Make(Test)

In this particular case, the compare function is not dependant on 'a type. The problem is that Set.Make cannot be applied to partial modules. Is there any way to make this kind of thing (ie : having a ('a Test.t )Set.t produced by Set.Make) ?

Thank you in advance for your responses ^^

2

a stupid query but is the 'a another_extern_type going to have an id record value?

4

In this case it will have it. To simplify, we could write the extern type as :

type 'a another_extern_type = {
    id : int;
    ... (* other things depending on 'a)
}
5

You could parameterize the application of Set.Make by a module that tells which 'a to choose.
For example (not tested):

module F(X: sig type t end) = struct
  module M = struct
    type t = X.t Test.t
    let compare = Test.compare
  end
  include Set.Make(M)
end

module N1 = F(Int)    (* sets whose elements have type int Test.t *)
module N2 = F(String) (* sets whose elements have type string Test.t *)
6

I think it doesn’t apply well in my case : I am working on a project where I don’t have control over 'a type (to be more precise, the module I am developing will be called on other modules that can have a different 'a )

7

As a workaround (and of course depending on the functionality you need from Set) you could use Map.Make with the id being the keys and the actual 'a another_extern_type the value.
In particular you have the Map.merge function that you can use to implement union, intersection and difference (provided your .id uniquely identify the whole value, as you seem to show by their use in compare).

8

If the type 'a doesn’t matter and the entire comparison is on some integer ID in those records, then you can use an existential GADT wrapper to put such elements into a set:

type 'a foo = {
  id: int;
  value: 'a;
}

module E =
struct
  type t = Foo: 'a foo -> t [@unboxed]
  let compare (Foo {id; _}) (Foo {id = id'; _}) = Int.compare id id'
end

module S = Set.Make (E)
3 Likes
9

The GADT wrapping looks good. It might be slightly annoying to use as any interaction with set elements will need to wrap or unwrap.

Does the [@unboxed] annotation guarantees that both E.t and foo have the same runtime representation and that the wrapping and unwrapping operations are no-ops after compilation?

10

Yes, the unboxed annotation allows to use wrapping with no runtime cost whatsoever.

11

A point that is maybe not obvious in @sim642 implementation is that it is essentially equivalent to
storing only the ids in the Set

module Set = struct
   include Set.Make(Int)
   let add x s = add x.id s
   let mem x s = mem x.id s
end

In particular, it is not possible to extract back a value from the set. If this is needed, another possible implementation would be to implement the set on top of a Map of ids:

let key x = x.Test.id

module Set: sig
  type 'a t
  val empty: 'a t
  val mem: 'a Test.t -> 'a t -> bool
  val add: 'a Test.t -> 'a t -> 'a t
  val choose: 'a t -> 'a Test.t
end = struct
   module Id_map = Map.Make(Int)
   type 'a t = 'a Test.t Id_map.t
   let empty = Id_map.empty
   let add x s = Id_map.add (key x) x s
   let mem x s = Id_map.mem (key x) s
   let choose s = snd (Id_map.choose s)
end