Dear All,

thanks for the pointer to the excellent paper.  First, let me say that my Vec data structure was born to fill a need I had while working on a project: while it has been useful to me, I certainly do not claim it is the best that can be done, so I am very grateful for these suggestions!

My Vec data structure is different from persistent arrays.  It is likely to be less efficient for get/set use.
However, it offers at logarithmic cost insertion/removal operations that are not present in the standard persistent arrays.
Consider a Vec a of size 10.
These operations are necessary if you want to use a Vec as a FIFO, for example (you append elements at the end, and you get the first element via Vec.pop 0 a).  In many algorithms, it is often handy to be able to remove/insert elements in the middle of a list.

In summary, I don't think the Vec data structure is a replacement for arrays or persistent arrays in numerically-intensive work.  But if you want a flexible data structure for the 90% of the code that is not peformance critical, they can be useful.
Now the question is: can one get better get/set efficiency while retaining the ability to insert/remove elements?  (I am sure that there is something better to be done...).

Luca

On 7/19/07, Hugo Ferreira <hmf@inescporto.pt> wrote:
Hello,

For those of you interested in functional array consider Sylvain Conchon
and Jean-Christophe Filliātre paper in [1]. The Union-Find (UF) uses
persistent arrays as its base data structure. I have made tests with the
UF using the code provided, an implementation of k-BUF data structure
(delayed backtracking) and altered version of the persistent array (fat
nodes + delayed backtracking). The tests I did show that this version of
persistent arrays is very efficient (especially for single threaded
backtracking).

Maybe Luca could pit his implementation against that of the article and
report on how they fare?

Regards,
Hugo Ferreira.

[1] http://www.lri.fr/~filliatr/ftp/publis/puf-wml07.ps

Loup Vaillant wrote:
> 2007/7/18, Luca de Alfaro < luca@dealfaro.org>:
>> Dear All,
>>
>> I would like to share with you an Ocaml implementation of extensible
>> arrays.
>>  The implementation is functional, based on balanced trees (and on the
>> code
>> for Set and Map); I called the module Vec (for vector - I like
>> short names).  You can find it at
>> http://www.dealfaro.com/home/vec.html
>> Module Vec provides, in log-time:
>>
>>  Access and modification to arbitrary elements ( Vec.put n el v puts
>> element
>> el in position n of vector v, for instance).
>> Concatenation
>> Insertion and removal of elements from arbitrary positions
>> (auto-enlarging
>> and auto-shrinking the vector).
>> as well as:
>>
>> All kind of iterators and some visitor functions.
>> Efficient translation to/from lists and arrays.
>> An advantage of Vec over List, for very large data structures, is that
>> iterating over a Vec of size n requires always stack depth bounded by
>> log n:
>> with lists, non-tail-recursive functions can cause stack overflows.
>>
>> I have been using this data structure for some months, and it has been
>> very
>> handy in a large number of occasions.  I hope it can be as useful to you.
>>
>> I would appreciate all advice and feedback.  Also, is there a repository
>> where I should upload it?  Do you think it is worth it?
>>
>> All the best,
>>
>> Luca
>
> Very interesting. I always felt uneasy about the presence of
> imperative arrays without a functional counterpart. I can't wait to
> try it.
>
> Looking at your array type definition, I assume that the timings you
> specified are worst-case? Is it possible to achieve better (but
> amortized) bounds? Do you think it would be worth the trouble?
>
> I didn't see in your specs the complexity of your iterators. Does
> these work in linear time, like those of the List and Array module?
>
> Regards,
> Loup
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs