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

[Vincent Aravantinos <vincent.aravantinos@gmail.com>]

[-- 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 --]