Re: [Caml-list] 'a Set?

[Jon Harrop <jon@jdh30.plus.com>]

On Wednesday 26 January 2005 15:36, Frédéric Gava wrote:
> ...
> Ok, I am agree.  It is just a remark about coherence of names of functions
> and
> interfaces of the modules in the stdlib. There is many ModuleName.S
> interfaces. Have the same names for functions that have the same semantics
> seems (to me) a good things. (for example, have a function cardinal  in the
> module Map, even if we could implemented this with a fold; the cardinal
> function of the Sets are could also be implemented with a fold)

There are several problems with this. Firstly, the name "cardinal". A set has 
cardinality. Lists and arrays have length. In C++ the equivalent function is 
"size". Should a map use one of those names or something else (is a map a 
_set_ of mappings? => "cardinal").

Secondly, there are numerous variants on a theme here. You suggest 
implementing Map.cardinal with a fold => O(n). This may be the best that can 
be done at the moment (assuming the internal representation stores maximum 
depth but not number of elements) but by storing the number of elements in 
all branches you could have O(1) "cardinal". Of course, there are other 
variants too (e.g. min = max = d depth => 2^d - 1 elements).

Ultimately, the core library is maintained by INRIA who can ill-afford to 
expend man-hours on adding arbitrary functionality to the core library. I 
would love to see such inclusions (and many others).

Perhaps I should make a webpage listing useful things for people to dabble 
on. :-)

Cheers,
Jon.