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

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

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

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.

   - Vec.insert 3 d a inserts value d in position 3 of a, shifting
   elements 3..9 of a to positions 4..10.
   - Vec.remove 3 a removes the element in position 3 of a, shifting
   elements 4..9 to positions 3..8.  Vec.pop is similar and returns the
   removed element as well.
   - Vec.concat works in log-time.

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
>

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