Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Vec: a functional implementation of extensible arrays
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2007-07-20 (16:45)
From: Brian Hurt <bhurt@j...>
Subject: Re: [Caml-list] Vec: a functional implementation of extensible arrays
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:

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