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

["Quôc Peyrot" <chojin@lrde.epita.fr>]

On Jun 27, 2007, at 9:48 PM, Brian Hurt wrote:

> 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.

If I have a tree/map datastructure and I add an element to it, my  
understanding it that, when building the new tree, all the node up to  
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  
only interested in the final result, i.e. I don't need to be able to  
rollback to a previous state or fancy stuff like that (I therefore  
never keep a reference to the root of the old tree, each time I add a  
new element).
Is there a way of writing the building code (with a fold-type of  
construct or something like that) such that the compiler will  
understand it, and will generate a code equivalent to the imperative  
code (i.e. we don't allocate new nodes up to the root each time we  
insert an element)?

-- 
Best Regards,
Quôc