* Re: module Set
1997-10-17 9:08 ` Xavier Leroy
@ 1997-10-17 13:46 ` Jean-Christophe Filliatre
1997-10-17 15:18 ` Judicael Courant
` (2 subsequent siblings)
3 siblings, 0 replies; 6+ messages in thread
From: Jean-Christophe Filliatre @ 1997-10-17 13:46 UTC (permalink / raw)
To: Xavier Leroy; +Cc: caml-list
> 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
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: module Set
1997-10-17 9:08 ` Xavier Leroy
1997-10-17 13:46 ` Jean-Christophe Filliatre
@ 1997-10-17 15:18 ` Judicael Courant
1997-10-17 15:38 ` Stefan Monnier
1997-10-20 8:04 ` Vincent Poirriez
3 siblings, 0 replies; 6+ messages in thread
From: Judicael Courant @ 1997-10-17 15:18 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: module Set
1997-10-17 9:08 ` Xavier Leroy
1997-10-17 13:46 ` Jean-Christophe Filliatre
1997-10-17 15:18 ` Judicael Courant
@ 1997-10-17 15:38 ` Stefan Monnier
1997-10-20 8:04 ` Vincent Poirriez
3 siblings, 0 replies; 6+ messages in thread
From: Stefan Monnier @ 1997-10-17 15:38 UTC (permalink / raw)
To: caml-list
[-- 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
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: module Set
1997-10-17 9:08 ` Xavier Leroy
` (2 preceding siblings ...)
1997-10-17 15:38 ` Stefan Monnier
@ 1997-10-20 8:04 ` Vincent Poirriez
3 siblings, 0 replies; 6+ messages in thread
From: Vincent Poirriez @ 1997-10-20 8:04 UTC (permalink / raw)
To: caml-list; +Cc: Jean-Christophe.Filliatre, 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.
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
^ permalink raw reply [flat|nested] 6+ messages in thread