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=AWL autolearn=disabled version=3.1.3 Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id A3B53BC6B for ; Wed, 27 Jun 2007 21:48:22 +0200 (CEST) Received: from smtp.janestcapital.com (www.janestcapital.com [66.155.124.107]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5RJmLmC002092 for ; Wed, 27 Jun 2007 21:48:22 +0200 Received: from [172.25.129.161] [38.96.172.125] by janestcapital.com with ESMTP (SMTPD-9.10) id AF15019C; Wed, 27 Jun 2007 15:48:37 -0400 Message-ID: <4682BF04.8090606@janestcapital.com> Date: Wed, 27 Jun 2007 15:48:20 -0400 From: Brian Hurt User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: =?ISO-8859-1?Q?Qu=F4c_Peyrot?= Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Book about functional design patterns 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> In-Reply-To: <342AAB2F-A76C-42C8-A5F1-4139BE2FE4A9@lrde.epita.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-Miltered: at discorde with ID 4682BF05.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; 0200,:01 lrde:01 computations:01 amortized:01 ocaml:01 runtime:01 allocations:01 ocaml:01 allocations:01 allocating:01 stack:01 long-time:01 allocating:01 stack:01 mutable:01 Quôc Peyrot wrote: > > On Jun 27, 2007, at 7:16 PM, Gabriel Kerneis wrote: > >> Le Wed, 27 Jun 2007 17:06:51 +0200, Quôc Peyrot >> a écrit : >> >>> It has been said multiple times on this >>> mailing list, but I think we really miss a book about these design >>> patterns and optimization tricks often specific to a given (or a set >>> of) feature (functional, lazy computations, garbage collector...). >> >> >> _Purely functional data structures_ by Chris Osaki might interest you. >> It's a very good book, covering lazy evaluation and persistent >> amortized data structures (among other things). Moreover, it does >> insist on optimizations (often left as exercises to the reader, with >> enough hints to be easy to figure out). > > > I have this book in my TOREAD list (for a long time now, my bad) > I must admit I don't use very often pure functional datastructures in > OCaml. > My main concern with functional programing has always been the > runtime hit > you get due to the extra memory allocations (which can be significant). In Ocaml, allocations are relatively cheap- a cost similiar to that of allocating on the stack. Which is why when you tell long-time Ocaml programmers that you want to avoid an allocation cost by allocating on the stack, they tend to go "um, why?" Mutable data structures have their cost as well. When you assign a pointer into an object old enough to be in the major heap, Ocaml kicks off a minor collection. For small N, this can often make O(log N) purely functional structures faster than their O(1) imperative counterparts. No to mention the correctness advantages, plus other advantages. Brian