[Camllist] Re: Sets and homemade ordered types
 Damien Guichard
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Damien Guichard <alphablock@o...> 
Subject:  [Camllist] Re: Sets and homemade ordered types 
Hi Matthias, I guess what you actually need is not a weird set datatype but some memoized function of type t > t. What i propose is the following code : type t = F of t  G of t * t  A  B let top_most () = let f = ref None and g = ref None in fun x > match x with  F _ > (match !f with None > f := Some x; x  Some y > y)  G _ > (match !g with None > g := Some x; x  Some y > y)  A > A  B > B Then top_most () gives you a function with the expected behavior. Hope it helps,  damien Damien Guichard 20090917 En réponse au message de : Matthias Puech du : 20090916 23:38:43 À : camllist@yquem.inria.fr CC : Sujet : Re: [Camllist] Sets and homemade ordered types 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. > 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 firstorder 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. Thanks for your answer anyway!  Matthias _______________________________________________ Camllist mailing list. Subscription management: http://yquem.inria.fr/cgibin/mailman/listinfo/camllist Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/camlbugs