module Set

module Set

[Jean-Christophe Filliatre]

Bonjour,

J'aimerai savoir  pourquoi dans le module  Set il est  dit que l'ordre
des elements renvoyes par  la fonction "elements" n'est pas  specifie,
alors  qu'en fait les elements  sont  tries (c'est un parcours prefixe
d'un arbre binaire de recherche). Meme remarque pour  iter et fold. Si
je le signale,  c'est que j'aimerai bien pouvoir  compter sur  le fait
que ces elements sont tries i.e.  pouvez-vous le specifier (et donc le
garantir) a partir de maintenant ? Merci d'avance.

[ english translation]

I would like  to know why, in  the module Set, it  is written that the
order  of  the elements  returned by  the  function  "elements" is not
specified, whereas the  elements are actually  sorted (it is a  prefix
traversal of a  binary search tree). Same remark  for iter and fold. I
would like to use this property  ; can't you  give us this property in
the module Set for the next release ? Thank you.

-- 
Jean-Christophe FILLIATRE
  mailto:Jean-Christophe.Filliatre@lri.fr
  http://www.lri.fr/~filliatr

Re: module Set

[Xavier Leroy]

> I would like  to know why, in  the module Set, it  is written that the
> order  of  the elements  returned by  the  function  "elements" is not
> specified, whereas the  elements are actually  sorted (it is a  prefix
> traversal of a  binary search tree).

Abstract data types have a specification and an implementation.
The specification usually does not specify everything about the
behavior of the implementation, if only to allow the implementation to
change later without breaking user's code.

In the case of Set, the ordering property you see is a consequence of
the implementation of sets as search trees.  But other implementations
(e.g. using hashing) would break that property.

> I would like to use this property  ; can't you  give us this property in
> the module Set for the next release ?

I'd rather not.  What you're looking for is not sets, but sets with
some extra ordering properties.  Don't use the generic Set package, then.
Use your own Ordered_set package.  (Feel free to cut and paste from
set.ml to implement it, of course.)  Well-defined abstract interfaces
are more important that code sharing, in my opinion.

- Xavier Leroy

Re: module Set

[Jean-Christophe Filliatre]

> Abstract data types have a specification and an implementation.
> The specification usually does not specify everything about the
> behavior of the implementation, if only to allow the implementation to
> change later without breaking user's code.
> 
> In the case of Set, the ordering property you see is a consequence of
> the implementation of sets as search trees.  But other implementations
> (e.g. using hashing) would break that property.

I perfectly agree. But I didn't ask for an interface specifying that
the implementation is based on AVL;  I was just asking for an interface
saying that the elements returned by "elements" are sorted. And it is
always possible to write such a function since the type of elements is
ordered (Independently from the implementation, it is always possible
to sort the lists of the elements of the set before returning it). 
The abstraction of the module Set is not endangered by this additional
property.

-- 
Jean-Christophe FILLIATRE
  mailto:Jean-Christophe.Filliatre@lri.fr
  http://www.lri.fr/~filliatr

Re: module Set

[Judicael Courant]

Hello,

>
>> I would like to use this property  ; can't you  give us this property in
>> the module Set for the next release ?
>
>I'd rather not.  What you're looking for is not sets, but sets with
>some extra ordering properties.  Don't use the generic Set package, then.
>Use your own Ordered_set package.  (Feel free to cut and paste from
>set.ml to implement it, of course.)  Well-defined abstract interfaces
>are more important that code sharing, in my opinion.
>

Then, I think everybody would be happy with the following solution :

- Jean-Christophe implements an Ordered_set package (by cuting and
  pasting the current Set);

- You integrate it into the next release;

- By the way, you take advantage of this new Ordered_set module to
  replace the implementation of Set by mine (set.mli remains
  unchanged of course) :

----------------------------------------------------------------------
(* set.ml *)
(* a very clever implementation of set.mli *)
(* generously put in the public domain by Judicael Courant *)

open Ordered_set

module type OrderedType= OrderedType
module type S = S

module Make = Make
(* That's all folks ! *)
----------------------------------------------------------------------

Hence, you have very-well defined abstract interfaces together with
code sharing. Isn't that a very good solution ?

:-)

Judicael.
-- 
Judicael.Courant@ens-lyon.fr, http://www.ens-lyon.fr/~jcourant/
tel : (+33) 04 72 72 82 28
Beware of bugs in the above code; I have only proved it correct, not tried it.
                -- Donald Knuth

Re: module Set

[Stefan Monnier]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 890 bytes --]

Xavier Leroy <Xavier.Leroy@inria.fr> writes:
> I'd rather not.  What you're looking for is not sets, but sets with
> some extra ordering properties.  Don't use the generic Set package, then.
> Use your own Ordered_set package.  (Feel free to cut and paste from
> set.ml to implement it, of course.)  Well-defined abstract interfaces
> are more important that code sharing, in my opinion.

Of course, you can have your cake and eat it too in the present case:
rename the current Set into OrderedSet (for instance) and then create
a Set module (now that the other one disappeared) as a wrapper around
OrderedSet.


        Stefan

----

Donc, en gros, au lieu de définir Set et OrderedSet indépendemment,, il suffit
de définir Set au-dessus de OrderedSet et comme ça on peut avoir le beurre et
l'argent du beurre: une interface propre et une bonne réutilisation du code.


        Stefan

Re: module Set

[Vincent Poirriez]

> 
> > I would like  to know why, in  the module Set, it  is written that the
> > order  of  the elements  returned by  the  function  "elements" is not
> > specified, whereas the  elements are actually  sorted (it is a  prefix
> > traversal of a  binary search tree).
> 
> Abstract data types have a specification and an implementation.
> The specification usually does not specify everything about the
> behavior of the implementation, if only to allow the implementation to
> change later without breaking user's code.
I agree with this
> 
> In the case of Set, the ordering property you see is a consequence of
> the implementation of sets as search trees.  But other implementations
> (e.g. using hashing) would break that property.

It seems to be an other reason of this property in the current
implementation.
The module Set does implement sets over "ordered" types. Which should
not
be the case in an hashtable based implementation I guess. To have an
implementation over ordered type with no specified ordered-fold function
can
be frustrating...

> 
> > I would like to use this property  ; can't you  give us this property in
> > the module Set for the next release ?
> 
> I'd rather not.  What you're looking for is not sets, but sets with
> some extra ordering properties.  Don't use the generic Set package, then.
> Use your own Ordered_set package.  (Feel free to cut and paste from
> set.ml to implement it, of course.)  Well-defined abstract interfaces
> are more important that code sharing, in my opinion.
> 

Why not provide three "new" functions : ordered_elements; ordered_fold
and
ordered_iter whith the same specification as the unordered ones except
that it should be precised that the elements are return or examined
using
the order Ord.compare. Of course, these functions should not be 
necesseraly available in an hashatble based implementation.

Vincent Poirriez


-- 
Tel: (33) {0}3 27 14 13 33   Fax: (33) {0}3 27 14 12 94
mailto:Vincent.Poirriez@univ-valenciennes.fr
 http://www.univ-valenciennes.fr/limav/poirriez
ISTV Université de Valenciennes Le Mont Houy BP 311 F59304 Valenciennes
CEDEX