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 nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78])
	by yquem.inria.fr (Postfix) with ESMTP id 907EBBC8A
	for <caml-list@yquem.inria.fr>; Sun, 30 Jan 2005 13:15:02 +0100 (CET)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j0UCF249019778
	for <caml-list@yquem.inria.fr>; Sun, 30 Jan 2005 13:15:02 +0100
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA16218 for <caml-list@pauillac.inria.fr>; Sun, 30 Jan 2005 13:15:01 +0100 (MET)
Received: from kraid.nerim.net (smtp-100-sunday.nerim.net [62.4.16.100])
	by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j0UCF1wl019773
	for <caml-list@inria.fr>; Sun, 30 Jan 2005 13:15:01 +0100
Received: from localhost (karryall.dnsalias.org [62.4.18.180])
	by kraid.nerim.net (Postfix) with ESMTP
	id 30F734190C; Sun, 30 Jan 2005 13:14:55 +0100 (CET)
Date: Sun, 30 Jan 2005 13:14:47 +0100 (CET)
Message-Id: <20050130.131447.71085960.oandrieu@nerim.net>
To: frederic.gava@wanadoo.fr
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Missing a function
From: Olivier Andrieu <andrieu@ijm.jussieu.fr>
In-Reply-To: <001901c506b1$7d89fb60$0100a8c0@mshome.net>
References: <001901c506b1$7d89fb60$0100a8c0@mshome.net>
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 nez-perce with ID 41FCCFC6.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Miltered: at nez-perce with ID 41FCCFC5.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 stdlib:01 functor:01 functor:01 ord:01 struct:01 ord:01 sig:01 val:01 expansive:01 ....:98 
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: 

 > Frédéric Gava [Sun, 30 Jan 2005]:
 > Hi,
 > >
 > > > 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)
 > > >
 > Hum. To remove an element, you have to test is its exists or not
 > before decrease n. It could be to much cost expansive...no ?

Oh right. And a test is needed for `add' too since the cardinal will
not change if the key is already bound in the map. So, all in all it's
not a very good idea :)

-- 
   Olivier