Re: module Set

From: Vincent Poirriez (Vincent.Poirriez@univ-valenciennes.fr)
Date: Mon Oct 20 1997 - 10:04:14 MET DST


Message-Id: <344B107E.BC7@univ-valenciennes.fr>
Date: Mon, 20 Oct 1997 08:04:14 +0000
From: Vincent Poirriez <Vincent.Poirriez@univ-valenciennes.fr>
To: caml-list@inria.fr
Subject: Re: module Set

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



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:12 MET