Re: [Ocaml-lib-devel] Another library for me to implement

[Brian H. <bh...@sp...>]

On Thu, 20 Mar 2003, Michal Moskal wrote:

> On Thu, Mar 20, 2003 at 11:30:08AM -0600, Brian Hurt wrote:
> > 
> > Ordered set.
> > 
> > Basically, a general balanced tree.  Insert, delete, search all O(log n), 
> > access nth element O(log n), convert to sorted list O(n).  
> 
> Like Set.Make?

No.  By definition, the Set in the standard library is *unordered*.  Take 
a look at the definition of iter, fold, etc.- the order that elements are 
presented are not defined.

Although it is implemented as an ordered set, and the current definition
wouldn't allow, for example, a hash table implementation (without some
deep trickery).  I'm not sure if we gain anything by pretending that it is
an unordered set.

Hmm.  And there's no way that I'm seeing to access the nth element cheaply 
(O(log n)).  elements gives you a sorted list of elements- you could then 
call nth on this.  A size function would also be nice.

Brian