[erlang-questions] list:join() for erlang?

[ok]

On 14 Sep 2007, at 9:11 pm, Bob Ippolito wrote:
> Sure, it works great for concatenating two lists, but it's not
> necessarily great for O(N^2) lists. Given that most of them will
> probably be short, I absolutely concede that ++ could very well be a
> performance winner in some cases. However, given that lists:reverse is
> special-cased I could imagine that lists:flatten could be also at some
> point and then the performance landscape could change dramatically.

(a) I repeat, you have misunderstood the advice about ++.
     In this particular problem, the version using ++ is not only
     linear in the size of the input, it is optimal:  it does
     fewer conses than the flatten version, and every single one
     of the conses it builds is a required part of the output.

     The thing is that (Xs++Ys)++Zs is inefficient compared with
     Xs++(Ys++Zs), and if you read the code I posted attentively,
     you will see that each and every instance of ++ is one of the
     Xs++(stuff) form, where Xs is one of the inputs.  That is the
     efficient case.

(b) I've done a few benchmarks, and the turning of reverse/1 into a
     BIF doesn't seem to have made much difference.  I have tried
     comparing my own reverse/1 (using an unrolled reverse/2) and
     found it difficult to measure any difference between that and
     flatten/2.

(c) Except for iolists, where the point is NOT to flatten,  
"unstructured"
     lists of the kind for which flatten makes sense are bad style in  
any
     programming language.  If anyone speeds up flatten, it will  
count as
     a sin in the Book of Life that they encouraged folly.

To cut a long story short, ++ is like a carving knife.  You have to
take reasonable care using it, but avoiding the carving knife and
tearing the roast you are serving to your friensd apart with your teeth
(like using flatten) would be messy and not likely to impress them
(to put it kindly).