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

[Fabrice Marchant <fabricemarchant@free.fr>]

  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