Building a Set module for elements of a Map

Building a Set module for elements of a Map

[Fabrice Marchant]

   Hi List !

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

  The problem is to access the OrderedType that permitted to build the Map M. It seems to have disappeared inside the output Map signature S. So the trial of regeneration :
struct type t = M.key let compare = compare end

  It maybe exists a straightforward signature we could pick somewhere inside Map related modules ?
  Moreover I'm afraid this "Ersatz" of signature based on _Pervasives_.compare is in some cases deficient, because different from original OrderedType of Map elements...

A parallel question for values type :
 how to declare inside F a module MValueSet to accomodate target elements of the input Map ?

Any light ?

Fabrice

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

[Jean-Christophe Filliâtre]

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
> 
>   The problem is to access the OrderedType that permitted to build the Map M. It seems to have disappeared inside the output Map signature S. So the trial of regeneration :
> struct type t = M.key let compare = compare end
> 
>   It maybe exists a straightforward signature we could pick somewhere inside Map related modules ?
>   Moreover I'm afraid this "Ersatz" of signature based on _Pervasives_.compare is in some cases deficient, because different from original OrderedType of Map elements...

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

Hope this helps,
-- 
Jean-Christophe Filliâtre
http://www.lri.fr/~filliatr/

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

[Xavier Leroy]

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

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

[Fabrice Marchant]

  Thanks for the useful and interesting answers !

Jean-Christophe Filliâtre explained:

> 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.)
  Your clearly exposed things with this example. I suspected my trial was not perfect. I now understand it is erroneous.

> 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  

I wanted to extend the functionalities of the Map module. Your solution perfectly suits what I need :

module MapPlus(K : Map.OrderedType) = struct
  module M = Map.Make(K)
  include M

  module MKeySet = Set.Make(K)

  let of_list l = List.fold_left (fun a (x, y) -> M.add x y a) M.empty l

  let domain map = M.fold (fun k _ -> MKeySet.add k) map MKeySet.empty
end

module StringMap = MapPlus.MapPlus( String )

let sm =
  StringMap.of_list ["one", 1;
                     "two", 2;
                     "three", 3]

let print l = Printf.printf "{%s}" (String.concat ", " l)

let _ =
  print (StringMap.MKeySet.elements (StringMap.domain sm))
(* -> {one, three, two} *)

Xavier Leroy wrote :

> 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

I discover ! Never have thought we could use 'with type elt' constraint this way.

----------------------------------------------------------------
  So you cleanly solved the problem to get the domain set of a map.
Please how would you build the module MValSet to express the range set of a map ?

( Inside MapPlus module, by :
let range map = M.fold (fun _ v -> MValSet.add v) map MValSet.empty
)

Regards,

Fabrice