David Allsopp wrote :
> Is it not possible to model your requirement using Map.Make instead - where
> the keys represent the equivalence classes and the values whatever data
> you're associating with them? 

Matthias Puech wrote:
>Yes, that's exactly the workaround I ended up using, although I'm not
>very happy with it because, among other things, these keys/class
>disciminant get duplicated (once inside the key, once inside the
>element). I'm getting more concrete below.

Since you already have the "compare" function between objects of
type t, why don't you make your map associate values of type t to
identical values of type t instead of trying to have different type
for keys and elements?

You can even do it generically, and obtain with little effort an
implementation of sets that supports find.

module Set_With_Find(X:Set.OrderedType) = 
struct
      module M = Map.Make(X)
      type t = X.t M.t (* with invariant that value v is always associated to v *)
      let find = M.find
      let add v s = M.add v v s
      .......
end

Pascal