Matthias Puech <pu...@cs.unibo.it> writes: > 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.
If your key is part of the value then you could use the value itself as key. You still get a key and a value but they would point to the same object in memory. >> 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! > > It seems to me rather natural to have it: otherwise, what's the point of > being able to provide your own compare, beside just checking for > membership of the class? The implementation of the function is > straightforward: just copy mem and make it return the element in case > of success: > > let rec find x = function > Empty -> raise Not_found > | Node(l, v, r, _) -> > let c = Ord.compare x v in > if c = 0 then v else > find x (if c < 0 then l else r) > > For union and inter, I don't see how their behavior would be undefined, > since neither the datastructure nor the functions are changed. > > > Here is what I want to do: Given a purely first-order datastructure, > let's say: > type t = F of t | G of t * t | A | B > I want to index values of type t according to their first constructor. > So in my set structure, there will be at most one term starting with > each constructor, and: > find (F(A)) (add (F(B)) empty) will return F(B) > > With a Set.find, it's easy: > > let compare x y = match x,y with > | (F,F | G,G | A,A | B,B) -> 0 > | _ -> Pervasives.compare x y > > module S = Set.Make ... > > With the Map solution, i'm obliged to define: > > type cstr = F' | G' | A' | B' > let cstr_of x = F _ -> F' | G _ -> G' etc. > > and then make a Map : cstr |--> t, which duplicates the occurrence of > the constructor (F' in the key, F in the element). Besides, I'm > responsible for making sure that the pair e.g. (G', F(A)) is not added. Don't define a cstr but use the t as key and value. You still need to make sure (A, B) isn't added but you can trivialy wrap the Map module with functions like let add m x = Map.add m x x that hide the duplication of key and value. The problem I see with your approach though is that you can't find m (F) but must use find m (F(A)) You need a dummy value for F to create a F key. Idealy I think type prefixes could solve your problem. But ocaml doesn't have them. MfG Goswin _______________________________________________ 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