From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.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 5E79FBB81 for ; Fri, 2 Dec 2005 22:11:32 +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 jB2LBV10027734 for ; Fri, 2 Dec 2005 22:11:32 +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 WAA00534 for ; Fri, 2 Dec 2005 22:11:31 +0100 (MET) Received: from smtp.cegetel.net (mf00.sitadelle.com [212.94.174.67]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jB2LBVrr005647 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Fri, 2 Dec 2005 22:11:31 +0100 Received: from [192.168.144.2] (unknown [84.6.181.206]) by smtp.cegetel.net (Postfix) with ESMTP id E1F181A5217; Fri, 2 Dec 2005 22:11:27 +0100 (CET) Message-ID: <4390B875.3080206@univ-savoie.fr> Date: Fri, 02 Dec 2005 22:11:17 +0100 From: Christophe Raffalli User-Agent: Mozilla Thunderbird 1.0.7 (X11/20051017) X-Accept-Language: fr, en MIME-Version: 1.0 To: caml-list Subject: Request for weak functional map ... X-Enigmail-Version: 0.93.0.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enig1724B3D4044A7FA971D76F37" X-Miltered: at concorde with ID 4390B883.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 4390B883.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; christophe:01 raffalli:01 christophe:01 raffalli:01 univ-savoie:01 logarithmic:01 bindings:01 bindings:01 trivial:01 reusing:01 logarithmic:01 hashtbl:01 nodes:01 usefull:01 rfc:02 X-Attachments: type="application/pgp-signature" name="signature.asc" name="signature.asc" X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO autolearn=disabled version=3.0.3 This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig1724B3D4044A7FA971D76F37 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Hi, It is a the second time I am in need for this ... Let me explain. I wish a data structure similar to the Map provided by standard library (logarithmic insertion and deletion) ... but with a "weak key" behavior: This means that when the key is no more accessible by the GC, all the bindings of this key are erased in all maps by the next GC. Typicaly, key will be records with a unique ID used for the comparison ... So when the key is no more accessible, you are sure the bindings to this key are useless. I think it is not trivial to implement this in the GC, but if you can have a removal in balanced tree that does no allocation (reusing the existing cell), then the sweep/copy phase of the GC could do the removal. BTW: I think this is impossible to implement using the Weak module ... but I am not so sure. (it may be possible to implement if you do not have the logarithmic requirement in complexity, but all insertiosn will copy a weak array and a standard array ... this is not reasonable). BTW2: there is also a solution with a weak array/hashtbl of all maps using a given key stored in the key record itself (you could point to the nodes of the balanced tree using the key, and wait the next insertion to rebalance the tree when deleting the key) ... then a finaliser could do the removal job ... But this does not look nice, because the data type for the key is not "free" anymore, and it also looks quite bad for the complexity. Are they other people that think this is a usefull feature to add to the language ? Is their functional languages that can do this ? Christophe --------------enig1724B3D4044A7FA971D76F37 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.2 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org iQIVAwUBQ5C4eJEBCSatcik9AQL5RQ//eZ4rFYmXXGx7xtYkSMulL9NywpCnJNFn 2JhmxGknZvjfKodS8Iu2+1N/gO8qmi2XtJluSy18XtFkfaNzcg56upOSzENPp54S vk4w3/MvOc8wgCI/wA/V1Nr46DWSdB6tTUATfIMQr5YMOWEyzFOW3cCim//W6h5b Nfr8k12CuCT08R9xD3j65wVQH2zeC8owMGK9HppN90hMkSRe81iZw585JOa0HRqt jsKY4YX4j7u+wAxMYAVsSR60d38DW5YpFMx8xYwLFDeSPUBWYcPRWYRuZqNzc+q1 3IWLB+h8629M7RYG5YNQ2MguZv1p9m8J3SHpt3xrTb4bwYiK93wRRPqWBedBOeIz mOyfMOdOZN29ZDWpKQrLxIhJZjuqe+gJ+vVK+fVH1zxm5hJiovnv9Xz0EEyU56Ev axhzN3sEsePqBYhfiGYjpjqcXld+jyIbvZwoYLqCNFIMhhDjqc3SWpT37j85cFcT Bnvh7VyosQOnu6vB3Y9GCprcS4BwP7mJVDhXDfS/48DBiLjQQiclT/VvXK7gsEv7 pFSOYPSdSvrOJ+nkYMO4XyOUYpIZ6+4r0eRfKFKWRtbOYvhSvvA9yIlAkZaRR0TU 8zPPDRVmwF7BnH7sYz/MIkg2MG7rbE4/K1pvF9+v6eF0q+c2W9ATsvfOhYdC9p4K kvTW3tzc3YM= =U7zF -----END PGP SIGNATURE----- --------------enig1724B3D4044A7FA971D76F37--