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 nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id CECE8BB91 for ; Sat, 23 Jul 2005 21:50:58 +0200 (CEST) Received: from 26.mail-out.ovh.net (26.mail-out.ovh.net [213.186.42.179]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j6NJowuq018245 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO) for ; Sat, 23 Jul 2005 21:50:58 +0200 Received: (qmail 7497 invoked by uid 503); 23 Jul 2005 19:51:00 -0000 Received: (QMFILT: 1.0); 23 Jul 2005 19:51:00 -0000 Received: from b6.ovh.net (HELO mail155.ha.ovh.net) (213.186.33.56) by 26.mail-out.ovh.net with DES-CBC3-SHA encrypted SMTP; 23 Jul 2005 19:51:00 -0000 Received: from b0.ovh.net (HELO queue-out) (213.186.33.50) by b0.ovh.net with SMTP; 23 Jul 2005 19:51:02 -0000 Received: from mail155.ha.ovh.net (10.0.50.155) by mail155.ha.ovh.net with SMTP; 23 Jul 2005 19:51:00 -0000 Received: from b0.ovh.net (HELO queue-pre) (213.186.33.50) by b0.ovh.net with SMTP; 23 Jul 2005 19:50:53 -0000 Received: from ppp-69-228-157-203.dsl.scrm01.pacbell.net (HELO trantor.glondu.net) (postmaster%glondu.net@69.228.157.203) by ns0.ovh.net with SMTP; 23 Jul 2005 19:50:53 -0000 From: Stephane Glondu Organization: Crans To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] How to do this properly with OCaml? Date: Sat, 23 Jul 2005 12:50:45 -0700 User-Agent: KMail/1.7.1 Cc: Thomas Fischbacher References: <200507231218.13166.Stephane.Glondu@crans.org> In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200507231250.45778.Stephane.Glondu@crans.org> X-Ovh-Remote: 69.228.157.203 (ppp-69-228-157-203.dsl.scrm01.pacbell.net) X-Ovh-Local: 213.186.33.20 (ns0.ovh.net) X-Miltered: at nez-perce with ID 42E29FA2.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 ocaml:01 heap:01 heap:01 garbage:01 wrote:01 underlying:01 element:02 element:02 seems:03 indeed:05 elements:05 removing:07 stephane:07 stephane:07 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.9 required=5.0 tests=FORGED_RCVD_HELO, RCVD_IN_BL_SPAMCOP_NET autolearn=disabled version=3.0.3 On Saturday 23 July 2005 12:35, Thomas Fischbacher wrote: > This seems to be equivalent to the idea of using an array option, which > I mentioned earlier. Indeed. > Problems: > > What if I have operations that add and remove elements on the heap in > random order (so that the heap sometimes has to shrink), and I want > (1) that every element which was removed from the heap and is otherwise > inaccessible can be reclaimed by GC, When you want to "remove" an element, you can put another (random) value from the same array at its place so that it can be garbage collected. If the remaining heap is empty (i.e. there is no other value to pick), you replace the Fill a with Empty n. > and (2) that removing a single > element from the heap does not require copying the underlying Array? This is a matter of algorithmics, isn't it? Stephane Glondu.