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

[Goswin von Brederlow <goswin-v-b@web.de>]

Matthias Puech <puech@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