Version française
Home     About     Download     Resources     Contact us    
Browse thread
module Set
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Vincent Poirriez <Vincent.Poirriez@u...>
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