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 LAA23285 for caml-redistribution; Mon, 20 Oct 1997 11:57:06 +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 PAA05244 for ; Fri, 17 Oct 1997 15:46:37 +0200 (MET DST) Received: from lri.lri.fr (root@lri.lri.fr [129.175.15.1]) by nez-perce.inria.fr (8.8.7/8.8.5) with ESMTP id PAA26339; Fri, 17 Oct 1997 15:46:33 +0200 (MET DST) Received: from sun-demons.lri.fr (sun-demons.lri.fr [129.175.8.90]) by lri.lri.fr (8.8.5/jtpda-5.2) with ESMTP id PAA06475 ; Fri, 17 Oct 1997 15:46:32 +0200 (MET DST) Received: by sun-demons.lri.fr (8.8.4/local) id PAA11819 ; Fri, 17 Oct 1997 15:46:30 +0200 (MET DST) Date: Fri, 17 Oct 1997 15:46:30 +0200 (MET DST) Message-Id: <199710171346.PAA11819@sun-demons.lri.fr> From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit To: Xavier Leroy Cc: caml-list@inria.fr Subject: Re: module Set In-Reply-To: <199710170908.LAA29437@pauillac.inria.fr> References: <199710151402.QAA06284@sun-demons.lri.fr> <199710170908.LAA29437@pauillac.inria.fr> Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) Sender: weis > 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 perfectly agree. But I didn't ask for an interface specifying that the implementation is based on AVL; I was just asking for an interface saying that the elements returned by "elements" are sorted. And it is always possible to write such a function since the type of elements is ordered (Independently from the implementation, it is always possible to sort the lists of the elements of the set before returning it). The abstraction of the module Set is not endangered by this additional property. -- Jean-Christophe FILLIATRE mailto:Jean-Christophe.Filliatre@lri.fr http://www.lri.fr/~filliatr