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

["Luca de Alfaro" <luca@dealfaro.org>]

[-- Attachment #1: Type: text/plain, Size: 3753 bytes --]

Reading the paper, I noticed that my name "put" for assigning a value to a
position is highly nonstandard.
I have changed it to "set" for version 1.1 of Vec.  Hopefully, changing so
soon will avoid confusion... sorry.

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
>

[-- Attachment #2: Type: text/html, Size: 5049 bytes --]