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

[Hugo Ferreira <hmf@inescporto.pt>]

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
>