Version franēaise
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Building a Set module for elements of a Map
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2008-06-27 (20:09)
From: Fabrice Marchant <fabricemarchant@f...>
Subject: Re: [Caml-list] Building a Set module for elements of a Map
  Thanks for the useful and interesting answers !

Jean-Christophe Filliātre explained:

> Using 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,
> 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

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
>  ...

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