* Re: [Caml-list] Building a Set module for elements of a Map
2008-06-25 13:30 Building a Set module for elements of a Map Fabrice Marchant
@ 2008-06-26 9:21 ` Jean-Christophe Filliâtre
2008-06-26 9:26 ` Xavier Leroy
2008-06-27 18:10 ` Fabrice Marchant
2 siblings, 0 replies; 4+ messages in thread
From: Jean-Christophe Filliâtre @ 2008-06-26 9:21 UTC (permalink / raw)
To: Fabrice Marchant; +Cc: caml-list
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/
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Caml-list] Building a Set module for elements of a Map
2008-06-25 13:30 Building a Set module for elements of a Map Fabrice Marchant
2008-06-26 9:21 ` [Caml-list] " Jean-Christophe Filliâtre
@ 2008-06-26 9:26 ` Xavier Leroy
2008-06-27 18:10 ` Fabrice Marchant
2 siblings, 0 replies; 4+ messages in thread
From: Xavier Leroy @ 2008-06-26 9:26 UTC (permalink / raw)
To: Fabrice Marchant; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [Caml-list] Building a Set module for elements of a Map
2008-06-25 13:30 Building a Set module for elements of a Map Fabrice Marchant
2008-06-26 9:21 ` [Caml-list] " Jean-Christophe Filliâtre
2008-06-26 9:26 ` Xavier Leroy
@ 2008-06-27 18:10 ` Fabrice Marchant
2 siblings, 0 replies; 4+ messages in thread
From: Fabrice Marchant @ 2008-06-27 18:10 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 4+ messages in thread