Version française
Home     About     Download     Resources     Contact us    
Browse thread
Re: Caml-list] Sets and home-made ordered types
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Matthias Puech <puech@c...>
Subject: Re: [Caml-list] Sets and home-made ordered types
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
>