Re: [Caml-list] Missing a function

[Radu Grigore <radugrigore@gmail.com>]

On Sat, 4 Dec 2004 15:13:44 +0100, Frédéric Gava
<frederic.gava@wanadoo.fr> wrote:

> > let cardinal e = fold (fun _ _ x -> succ x) e 0;;
> [...] Map are also implemented as balanced
> tree (like sets) and therefore, it is easy to add a function of "cardinal".

I agree it's strange not to have "cardinal" in Map.Make. The
implementations of Set and Map are likely to be very similar anyway.

I do not have the ocaml sources handy right now but... Set and Map are
probably RB-trees. In this case there are at least 2 pointers for
links (left and right children),  one pointer for key and, for maps,
one pointer for data.  So a set of N elements occupies at least 12xN
bytes, while a map occupies at least 16xN bytes. If an element counter
is added then the sizes would increase to 16xN and 20xN. That doesn't
seem too bad. The advantages would be:

a. O(1) cardinal function. Right now for Map the user can implement a
O(n) one and for Set the complexity isn't specified. It is probably
O(lg n).

b. O(lg n) indexed access.

Such a change implies minimal modification of existing functions:
Set.cardinal becomes faster (if my guess -- lg n -- was correct) and
add/remove will be _slightly_ slower. The advantage would be
Map.cardinal and indexed access.

-- 
regards,
 radu
http://rgrig.idilis.ro/