Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

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: 1997-10-17 (12:17)
From: Xavier Leroy <Xavier.Leroy@i...>
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.

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 to implement it, of course.)  Well-defined abstract interfaces
are more important that code sharing, in my opinion.

- Xavier Leroy