Sets and home-made ordered types

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...

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

[Matthias Puech]

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] Re: Sets and home-made ordered types

[Damien Guichard]

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

Hi Matthias,

I guess what you actually need is not a weird set datatype but some memoized function of type t -> t.

What i propose is the following code :

type t = F of t | G of t * t | A | B

let top_most () =
  let f = ref None and g = ref None in
  fun x ->
  match x with
  | F _ -> (match !f with None -> f := Some x; x | Some y -> y) 
  | G _ -> (match !g with None -> g := Some x; x | Some y -> y)
  | A -> A
  | B -> B

Then top_most () gives you a function with the expected behavior.

Hope it helps,

- damien




Damien Guichard
2009-09-17



En réponse au message
de : Matthias Puech
du : 2009-09-16 23:38:43
À : caml-list@yquem.inria.fr
CC : 
Sujet : Re: [Caml-list] Sets and home-made ordered types


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:
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

[-- Attachment #2: Type: text/html, Size: 10026 bytes --]

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

[Vincent Aravantinos]

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


Le 16 sept. 09 à 23:38, Matthias Puech a écrit :

>> 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?

I think that the ability to define your own 'compare' function in the  
original
Set module is more there to deal with different *orders* rather than  
different
equalities.

> 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.

But maybe that's not so much of a duplicate that you think.
Actually cstr is the type of your class equivalence on type t.
It happens that you can have a representative for each class
equivalence, which you store in your map, but that's not the class
equivalence itself.

What I mean is that if you see this through this particular
interpretation, it's rather natural to have two types for two different
kinds of objects. I think furthermore that this is easier to reason
about. For instance the 'compare' function you define is actually not
meant to compare objects of type t but their equivalence class
representatives. Defining a good compare when reasoning about type t
may be hard while when you are aware that you actually want a compare
between class representatives this can turn out to be much easier
(I ran recently in this kind of problem and this was definitely the
case). Actually that's just one of the usual advantages of using
distinct types to represent distinct notions. But your problem being
trivially solved by your extension of Set with a 'find' function I
understand that you would prefer this solution.

Cheers,
--
Vincent Aravantinos
PhD Student - LIG - CAPP Team
Grenoble, France
+33.6.11.23.34.72
vincent.aravantinos@imag.fr
http://membres-lig.imag.fr/aravantinos/


[-- Attachment #2: Type: text/html, Size: 6457 bytes --]

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

[David Allsopp]

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

While I agree that the duplication is unfortunate, it is only one word (the
number needed in each instance to store the Constructor value for the key -
you get the Constructor "for free" with a tuple as it's "stored" in the tag
of the block allocated to hold the tuple.)

> > 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!

<snip - see other posts>

> For union and inter, I don't see how their behavior would be undefined,
> since neither the datastructure nor the functions are changed.

The element put into the sets on intersection and union is undefined. Say
you have the trivial case with just one equivalence class 

type u = A of int
module MySet = Set.Make(struct type t = u let compare x y = 0 end)

So your sets will all be singletons. What is the result of:

MySet.inter (MySet.singleton (A 1)) (MySet.singleton (A 2))

In 3.11.1, it's the singleton set containing [A 2] but the definition
intersection reasonably allows for it to be [A 1] instead. However, this of
itself isn't an argument against having [find] - it's just that what you're
doing already isn't really a set.

<snip>

> Besides, I'm responsible for making sure that the pair e.g. (G', F(A)) is
not added.

Jacques Garrigue has a syntax extension (PolyMap, I think is its name) which
may help you here - it allows you to enforce this invariant automatically
(and provides neater syntax for it). But I agree that for your case adding a
"find" method to a custom (i.e. copied) version of Set is probably the way
forward - I'm just not sure that you'll convince the guys at Inria to add
the method to the standard library's version of Set.Make!


David

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

[Goswin von Brederlow]

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

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
>