Re: [Caml-list] Building a Set module for elements of a Map

[Xavier Leroy <Xavier.Leroy@inria.fr>]

Fabrice Marchant wrote:

> Please consider a functor F that takes as input the output signature of a Map.
>
> Here is the only way I see to declare a Set module whose elements type are
Map.S.key :
>
> module F ( M : Map.S ) = struct
>   module MKeySet =
>     Set.Make ( struct type t = M.key let compare = compare end )
> end

Jean-Christophe Filliâtre replied:

> Using Pervasives.compare instead of a user-defined comparison function
> may even be incorrect. (Suppose the intended comparison function should
> identify (x,y) and (y,x), for instance; obviously, Pervasives.compare
> will not.)
>
> A possible solution to your problem is to have functor F taking instead
> a module for keys as argument, and then to build module M inside F; thus
> it would look like:
>
> 	module F(K : OrderedType) = struct
> 	  module M = Map.Make(K)
> 	  module MKeySet = Set.Make(K)
> 	  ...
> 	end

Jean-Christophe is right that Pervasives.compare is not the solution.

Yet another alternative is to parameterize F over both a Map and a Set,
adding a sharing constraint to ensure that they work on compatible
data types:

module F (M: Map.S) (MKeySet: Set.S with type elt = M.key) = struct
  ...
end

- Xavier Leroy