Re: [Caml-list] Sets and home-made ordered types

[Matthias Puech <puech@cs.unibo.it>]

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