Heap based mutable arrays?

[Thomas Lindgren]

> Would you include the declarative bit in the "right complexity"?

Well, the point was just that you can translate an existing imperative
algorithm fairly easily (if verbosely) into Erlang _and_ get good complexity.
You can do the translation part today with an appropriate ADT:

    /* A[I] = A[M]+A[N] */
    ...
    V1 = read(Array0,M),
    V2 = read(Array0,N),
    Array1 = write(Array0,I,M+N),  %% now use Array1 from here on
    ...

But space/time complexity will of course depend on how read/2 and
write/3 are implemented. Getting the right complexity for both reads
and writes is the problem solved by declarative vectors.

The complexity of implementing the algorithm stays about the same,
though debugging may be easier since old versions can be kept around
for inspection. (Having a verbose notation for array access may make
implementation harder, due to syntactic clutter; erl_lint could
perhaps be extended to warn about bad use of old versions.)

		       Thomas
-- 
Thomas Lindgren					thomas+junk@REDACTED
Alteon WebSystems