Re: [Caml-list] Book about functional design patterns

[Brian Hurt <bhurt@janestcapital.com>]

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 <chojin@lrde.epita.fr>
>> 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