From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA23366 for caml-redistribution; Mon, 20 Oct 1997 12:00:37 +0200 (MET DST)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id JAA19732 for <caml-list@pauillac.inria.fr>; Mon, 20 Oct 1997 09:07:37 +0200 (MET DST)
Received: from pulsar.univ-valenciennes.fr (pulsar.univ-valenciennes.fr [193.50.192.1])
	by nez-perce.inria.fr (8.8.7/8.8.5) with ESMTP id JAA02250;
	Mon, 20 Oct 1997 09:07:34 +0200 (MET DST)
Received: from titan.univ-valenciennes.fr (root@titan [193.50.192.38])
          by pulsar.univ-valenciennes.fr (8.8.5/jtpda-5.2) with SMTP id JAA01684
          ; Mon, 20 Oct 1997 09:08:58 +0100 (WET DST)
Received: from titan (localhost) by titan.univ-valenciennes.fr (5.x/SMI-SVR4)
	id AA08854; Mon, 20 Oct 1997 08:04:16 GMT
Message-Id: <344B107E.BC7@univ-valenciennes.fr>
Date: Mon, 20 Oct 1997 08:04:14 +0000
From: Vincent Poirriez <Vincent.Poirriez@univ-valenciennes.fr>
Organization: limav
X-Mailer: Mozilla 3.01Gold (X11; I; SunOS 5.4 sun4m)
Mime-Version: 1.0
To: caml-list@inria.fr
Cc: Jean-Christophe.Filliatre@lri.fr, Xavier Leroy <Xavier.Leroy@inria.fr>
Subject: Re: module Set
References: <199710170908.LAA29437@pauillac.inria.fr>
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
Sender: weis

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