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

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

[CUOQ Pascal]

[-- Attachment #1: Type: text/plain, Size: 1091 bytes --]


David Allsopp wrote :
> 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? 

Matthias Puech wrote:
>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.

Since you already have the "compare" function between objects of
type t, why don't you make your map associate values of type t to
identical values of type t instead of trying to have different type
for keys and elements?

You can even do it generically, and obtain with little effort an
implementation of sets that supports find.

module Set_With_Find(X:Set.OrderedType) = 
struct
      module M = Map.Make(X)
      type t = X.t M.t (* with invariant that value v is always associated to v *)
      let find = M.find
      let add v s = M.add v v s
      .......
end

Pascal




[-- Attachment #2: winmail.dat --]
[-- Type: application/ms-tnef, Size: 3196 bytes --]

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

[Matthias Puech]

Hello and thanks to all for your answers,

If I understand correctly, you're all (David, Elnatan, Vincent, 
Tiphaine, Pascal) suggesting more or less the same solution (the one 
below). Do you have an idea of its memory overhead compared to just 
using Sets? I guess the value is not copied twice but shared between 
keys and elements right? So what, one pointer more for each association 
in the Map? That would be rather acceptable (but still not ideal, sorry 
I'm very demanding).

Thanks again,

    -- Matthias

CUOQ Pascal a écrit :
> Since you already have the "compare" function between objects of
> type t, why don't you make your map associate values of type t to
> identical values of type t instead of trying to have different type
> for keys and elements?
>
> You can even do it generically, and obtain with little effort an
> implementation of sets that supports find.
>
> module Set_With_Find(X:Set.OrderedType) = 
> struct
>       module M = Map.Make(X)
>       type t = X.t M.t (* with invariant that value v is always associated to v *)
>       let find = M.find
>       let add v s = M.add v v s
>       .......
> end
>
> Pascal
>
>
>
>   
> ------------------------------------------------------------------------
>
> _______________________________________________
> 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
>   

Re: Sets and home-made ordered types

[CUOQ Pascal]

> So what, one pointer more for each association 
> in the Map? That would be rather acceptable (but still not ideal, sorry 
> I'm very demanding).

You were already paying the price of "one pointer more"
many times over and were not even thinking about it. One
more will not make any difference.

You have to realize that each node already carries a height,
two pointers to subtrees, and take into account the one-word
overhead for the block header. We're not doubling the size of
each tree node here, we're increasing it from 5 to 6 words.

Pascal
PS: You make up for the overhead by having dynamic structures
that are just the right size, and by taking advantage of sharing,
of course.

Sets and home-made ordered types

[Matthias Puech]

Dear Camlists,

This is my first post on this list, so please excuse me if it is too 
vague/off-topic/already discussed... I've been asking myself this 
question about the standard library's Set for quite a while.

The ability of the module Set to take an order (compare) as input, 
possibly larger than Pervasive's one, allows for some valuable tricks, 
i.e. assure that a set contains at most one element of each equivalence 
class. This element is actually stored in the structure, but then it 
seems not possible to retreive it (efficiently): the only interaction is 
to test if some element of the same equivalence class is present, with 
mem : elt -> t -> bool.

My question is : why isn't there a function find : elt -> t -> elt, 
where find e s would return the stored element  e' s.t compare e e' = 1 
? These two elements can be interestingly distinct though...

Thanks in advance for all enlightenment.

    --Matthias

PS: Of course I don't want to fold, filter or such, for efficiency 
reasons...