From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <pierre.weis@inria.fr>
Delivered-To: caml-list@yquem.inria.fr
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39])
	by yquem.inria.fr (Postfix) with ESMTP id A94D5BC88
	for <caml-list@yquem.inria.fr>; Sat, 29 Jan 2005 22:05:49 +0100 (CET)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j0TL5nIW001548
	for <caml-list@yquem.inria.fr>; Sat, 29 Jan 2005 22:05:49 +0100
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA24365 for <caml-list@pauillac.inria.fr>; Sat, 29 Jan 2005 22:05:48 +0100 (MET)
Received: from kraid.nerim.net (smtp-106-saturday.nerim.net [62.4.16.106])
	by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j0TL5mWk001545
	for <caml-list@inria.fr>; Sat, 29 Jan 2005 22:05:48 +0100
Received: from localhost (karryall.dnsalias.org [62.4.18.180])
	by kraid.nerim.net (Postfix) with ESMTP
	id 7B8D9418B9; Sat, 29 Jan 2005 22:05:46 +0100 (CET)
Date: Sat, 29 Jan 2005 22:05:47 +0100 (CET)
Message-Id: <20050129.220547.41630437.oandrieu@nerim.net>
To: radugrigore@gmail.com
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Missing a function
From: Olivier Andrieu <andrieu@ijm.jussieu.fr>
In-Reply-To: <7f8e92aa05012911345344cbc6@mail.gmail.com>
References: <41B1BAD4.2000004@yahoo.fr>
	<003601c4da0b$774ac220$0100a8c0@mshome.net>
	<7f8e92aa05012911345344cbc6@mail.gmail.com>
X-Mailer: Mew version 4.1 on Emacs 21.3 / Mule 5.0 (SAKAKI)
Mime-Version: 1.0
Content-Type: Text/Plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Miltered: at concorde with ID 41FBFAAD.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Miltered: at concorde with ID 41FBFAAC.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; caml-list:01 andrieu:01 andrieu:01 ijm:01 gava:01 gava:01 wrote:01 stdlib:01 functor:01 functor:01 ord:01 struct:01 ord:01 sig:01 val:01 
X-Spam-Checker-Version: SpamAssassin 3.0.0 (2004-09-13) on yquem.inria.fr
X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled 
	version=3.0.0
X-Spam-Level: 

 > 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