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

But that is TOTALLY irrelevant to the algorithm we have been
discussing, where the total cost, using ++, is LINEAR in the
total size of the input.  The use of flatten will in NO WAY
improve the performance for THIS particular problem.

Basically, if you arrange your recursive code so that
whenever there is E1 ++ E2 you also have E1 is part of
the input (and never used again) while E2 may be recursively
> 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.
> Either way, as I said before, this is absolutely not a bottleneck in
> our code so we didn't try very many implementations.
>
>>>
>>> This is our join/2, which is largely the same but uses  
>>> lists:flatten/1
>>> instead of ++:
>>
>> But that changes the semantics.  It will accept stuff that I did not
>> at all wish my code to accept.
>
> lists:append/1 could be used in this case, but I saw no good reason to
> specialize. If your code has incorrect input somewhere a library
> function such as this is probably not the best place to figure that
> out.
>
>>> join([S], _Separator) ->
>>>     lists:flatten(S);
>>
>> This does *more* copying than the ++ version.
>
> This is a degenerate case where practically nothing happens in any
> version, so it's hardly worth mention.
>
> -bob