[erlang-questions] Strings as Lists

[Kevin Scaldeferri]

On Feb 14, 2008, at 7:06 PM, Richard A. O'Keefe wrote:

> 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).


Pardon my ignorance, but how it is that concatenating to the end of a  
length n immutable list is not O(n)?  Isn't it necessary to copy all  
the list elements?

(It's also worth noting that while strictly speaking the append on a  
mutable array is O(m), in practice the coefficient is very small since  
it's implemented as a single memcpy.)


-kevin