Matthias Puech wrote: > David Allsopp a écrit : > > 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? > > 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.
While I agree that the duplication is unfortunate, it is only one word (the number needed in each instance to store the Constructor value for the key - you get the Constructor "for free" with a tuple as it's "stored" in the tag of the block allocated to hold the tuple.) > > In terms of a strictly pure implementation of a functional Set, it > > would be odd to have a "find" function - you'll also get some interesting > > undefined behaviour with these sets if you try to operations like union and > > intersection but I guess you're already happy with that! <snip - see other posts> > For union and inter, I don't see how their behavior would be undefined, > since neither the datastructure nor the functions are changed. The element put into the sets on intersection and union is undefined. Say you have the trivial case with just one equivalence class type u = A of int module MySet = Set.Make(struct type t = u let compare x y = 0 end) So your sets will all be singletons. What is the result of: MySet.inter (MySet.singleton (A 1)) (MySet.singleton (A 2)) In 3.11.1, it's the singleton set containing [A 2] but the definition intersection reasonably allows for it to be [A 1] instead. However, this of itself isn't an argument against having [find] - it's just that what you're doing already isn't really a set. <snip> > Besides, I'm responsible for making sure that the pair e.g. (G', F(A)) is not added. Jacques Garrigue has a syntax extension (PolyMap, I think is its name) which may help you here - it allows you to enforce this invariant automatically (and provides neater syntax for it). But I agree that for your case adding a "find" method to a custom (i.e. copied) version of Set is probably the way forward - I'm just not sure that you'll convince the guys at Inria to add the method to the standard library's version of Set.Make! David _______________________________________________ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
