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 OAA02938 for caml-redistribution; Fri, 17 Oct 1997 14:17:11 +0200 (MET DST)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA29445 for <caml-list@pauillac.inria.fr>; Fri, 17 Oct 1997 11:08:46 +0200 (MET DST)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.8.7/8.8.5) with ESMTP id LAA23958;
	Fri, 17 Oct 1997 11:08:44 +0200 (MET DST)
Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id LAA29437; Fri, 17 Oct 1997 11:08:43 +0200 (MET DST)
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)
Cc: caml-list@inria.fr
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
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.

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