On 7/19/07, Loup Vaillant <loup.vaillant@gmail.com> 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