From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 255F5BC6B for ; Wed, 27 Jun 2007 22:04:10 +0200 (CEST) Received: from smtp2e.orange.fr (smtp2e.orange.fr [80.12.242.111]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5RK49Ul005352 for ; Wed, 27 Jun 2007 22:04:09 +0200 Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf2e04.orange.fr (SMTP Server) with ESMTP id A1836700008C for ; Wed, 27 Jun 2007 22:04:09 +0200 (CEST) Received: from [192.168.1.162] (ALagny-153-1-98-23.w90-3.abo.wanadoo.fr [90.3.145.23]) by mwinf2e04.orange.fr (SMTP Server) with ESMTP id 7C1BB7000088 for ; Wed, 27 Jun 2007 22:04:09 +0200 (CEST) X-ME-UUID: 20070627200409508.7C1BB7000088@mwinf2e04.orange.fr Mime-Version: 1.0 (Apple Message framework v752.2) In-Reply-To: <4682BF04.8090606@janestcapital.com> References: <200706271314.35134.jon@ffconsultancy.com> <1A1D6F56-B3DB-4552-969C-9859482175AC@lrde.epita.fr> <46826C69.5060802@functionality.de> <20070627191633.73ab011a@kerneis.info> <342AAB2F-A76C-42C8-A5F1-4139BE2FE4A9@lrde.epita.fr> <4682BF04.8090606@janestcapital.com> Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed Message-Id: Content-Transfer-Encoding: quoted-printable From: =?ISO-8859-1?Q?Qu=F4c_Peyrot?= Subject: Re: [Caml-list] Book about functional design patterns Date: Wed, 27 Jun 2007 22:04:07 +0200 To: caml-list@yquem.inria.fr X-Mailer: Apple Mail (2.752.2) X-Miltered: at discorde with ID 4682C2B9.002 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; lrde:01 ocaml:01 allocations:01 allocating:01 stack:01 long-time:01 ocaml:01 allocating:01 stack:01 mutable:01 pointer:01 node:01 compiler:01 nodes:01 2007,:98 On Jun 27, 2007, at 9:48 PM, Brian Hurt wrote: > In Ocaml, allocations are relatively cheap- a cost similiar to that =20= > of allocating on the stack. Which is why when you tell long-time =20 > Ocaml programmers that you want to avoid an allocation cost by =20 > allocating on the stack, they tend to go "um, why?" > > Mutable data structures have their cost as well. When you assign a =20= > pointer into an object old enough to be in the major heap, Ocaml =20 > kicks off a minor collection. For small N, this can often make O=20 > (log N) purely functional structures faster than their O(1) =20 > imperative counterparts. > > No to mention the correctness advantages, plus other advantages. If I have a tree/map datastructure and I add an element to it, my =20 understanding it that, when building the new tree, all the node up to =20= the root are going to be replaced. Is my understanding correct? Now let's say I want to build a tree with millions elements, and I'm =20 only interested in the final result, i.e. I don't need to be able to =20 rollback to a previous state or fancy stuff like that (I therefore =20 never keep a reference to the root of the old tree, each time I add a =20= new element). Is there a way of writing the building code (with a fold-type of =20 construct or something like that) such that the compiler will =20 understand it, and will generate a code equivalent to the imperative =20 code (i.e. we don't allocate new nodes up to the root each time we =20 insert an element)? --=20 Best Regards, Qu=F4c