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 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.
Thanks for your answer anyway!
-- Matthias
_______________________________________________
Caml-list mailing list. Subscription management: