[erlang-questions] Strings as Lists

[Richard A. O'Keefe]

I wrote:
>> No, it has to do with the fact that appending on the right is O(n)
>> whether one uses lists or arrays.

Since this is the *Erlang* mailing list, this should have been read as
"whether one uses (immutable) lists or (immutable) arrays".

On 14 Feb 2008, at 8:37 pm, Alpár Jüttner wrote:
> A minor correction: appending at the end of an array  
> (std::vector<>) is
> O(1) operation in C++.

std::vector<> is not a class of immutable arrays.
Suppose we have two byte-strings of length n and m.
If they are immutable, the concatenation cost is O(n+m).
If you are willing to smash the one on the left, and it is "stretchy",
the cost is STILL not O(1), it is O(m).

The technique Alpár Jüttner discussed is, or should be, in chapter 1  
or 2
of any good data structures and algorithms book.
>
> All of these C++ counterparts requires unmeasurably low time ( <  
> 4ms) on
> my laptop:

And they all do it by doing something wildly irrelevant to Erlang:
SMASHING a mutable data structure.

Last year, on the same general topic, someone mentioned Phil Bagwell's
VList data structure.  Annoyingly, his paper doesn't really analyse the
asymptotic performance of most operations.  His comparison tables give
specific times on specific machines for specific problems, not general
formulas.  He says that they could be made to support additions at  
either
end but doesn't go into detail.  Anyway, that could be quite a good
structure for adding small amounts of text at either end, but I don't  
think
it would handle general concatenation well.  There *are* sequence data
structures in the functional community that handle concatenation well.