From: Xavier Leroy <Xavier.Leroy@inria.fr>
Message-Id: <199710170908.LAA29437@pauillac.inria.fr>
Subject: Re: module Set
In-Reply-To: <199710151402.QAA06284@sun-demons.lri.fr> from Jean-Christophe Filliatre at "Oct 15, 97 04:02:45 pm"
To: Jean-Christophe.Filliatre@lri.fr
Date: Fri, 17 Oct 1997 11:08:42 +0200 (MET DST)
> 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
This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:12 MET