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

["Loup Vaillant" <loup.vaillant@gmail.com>]

2007/7/19, Luca de Alfaro <luca@dealfaro.org>:
>
> For get/set, the worst case and the average case are both logarithmic: it's
> a balanced tree (if you are lucky, you can find your answer at the root!

I did. :)

> ;-).  I am open to new ideas.  In part, I wanted a simple data structure
> (easier to extend, among other things).  Also, I use Set, Map, etc, quite
> often, and those are also balanced trees: I thought that if I can live with
> those, I can probably live with Vec as well.

So can I. Your current implementation is already very attractive, and
looks very usable. For the new idea, have you thought of making (or
specifying) syntactic sugar to use your array?

About improving performance, here is my guess : there is no way to
lower the bounds on get and set. However, the average cost of insert
may already be O(1), provided you use your array the same way you
would use an imperative version of it (more accurately, not inserting
an element to an old version of your array). The same may be true for
remove.

Therefore, if I guess right, to take advantage of persistence AND have
insert perform in O(1) average, you would have to use (and pay for)
lazy evaluation. How, I don't know (yet).

(Note that I have stolen this idea from Okasaki's book)

> For an iterator, the worst case is as follows, where n is the size of the
> Vec:
>
> if you iterate on the whole Vec, then O(n)
> if you iterate over m elements (you can iterate on a subrange), then O(m +
> log n).
> That's why I have iterators: you can also iterate via a for loop, using get
> to access the elements, but then the time becomes O(n log n) for the first
> case, and O(m log n) for the second case.

That is why I wondered if lazy evaluation was worth the trouble at all
: most of the time, we iterate rather than insert or remove elements.
I only regret the absence of filter. Is there a way to obtain a
efficient filter? (Well, if my guess above is right, a naive
implementation of filter would already be quite efficient...)

Regards,
Loup