[erlang-questions] Strings as Lists

[Richard A.O'Keefe]

On 16 Feb 2008, at 8:20 am, Kevin Scaldeferri wrote:
>
> 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.
>
> 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?

As you can see from the quoted text above, that's EXACTLY what I said.
>
> (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.)

memcpy() isn't that fast.

By using suitable (immutable) trees, you can get concatenation down  
to O(1)
while still keeping random access to O(lg n).  The way Erlang (ab) 
uses lists
as "iolists" you can get concatenation in O(1) followed by O(n)  
flattening,
so it's easy for an Erlang program to build a string cheaply in  
either left
to right or right to left order using lists, but wouldn't be using  
binaries.