Sets and homemade ordered types

Matthias Puech

Matthias Puech
 Vincent Aravantinos
 David Allsopp
 Goswin von Brederlow

Matthias Puech
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20090917 (07:31) 
From:  Vincent Aravantinos <vincent.aravantinos@g...> 
Subject:  Re: [Camllist] Sets and homemade ordered types 
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://membreslig.imag.fr/aravantinos/