Re: [Caml-list] Vec: a functional implementation of extensible arrays

[Brian Hurt <bhurt@janestcapital.com>]

Luca de Alfaro wrote:

>
>
> This is almost easy.  I would need to add a bit to each node to keep 
> track of whether it's balanced...
> The penalty would be that the balancing function would need to do 
> slightly more work to find out what has to be balanced.
> So perhaps it's not a good idea for append, insert, but it could make 
> sense for concat (?), and especially for filter and sub...
> But I am hesitant.  If one does concat, or one does sub to extract a 
> sub-array, I wrote the code already so that sharing is maximized. What 
> is the percentage of cases in which you get a Vec, but then don't do 
> any get/set on it, and only iterate?
> Especially since you already have iterators on subranges?  Do you 
> think it's worth it?  Anyone has advice?

I don't think that with laziness you can avoid enough work to make 
inserts O(1).

On the other hand, sub and filter can be done in O(M + log N) easily 
enough, see:
http://citeseer.ist.psu.edu/236207.html

The paper is about red-black trees, but it's applicable to all 
rotation-balanced trees.

Brian