Re: [Caml-list] Missing a function

[Olivier Andrieu <andrieu@ijm.jussieu.fr>]

 > Radu Grigore [Sat, 29 Jan 2005]:
 > 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.

Another option is to build on top of the stdlib Map functor another
functor that keeps track of the cardinal of a map :

module CMap = functor (Ord : Map.OrderedType) ->
  (struct
    module M = Map.Make (Ord)
	
    type key = M.key
    type 'a t = int * 'a M.t

    let cardinal = fst

    let empty = 0, M.empty

    let add k v (n, m) = (n + 1, M.add k v m)

    let find k (_, m) = M.find k m
	  
	....
   : sig
       include Map.S
       val cardinal : 'a t -> int
     end)

-- 
   Olivier