[erlang-questions] foldl vs foldr and ++

[Andrew Ledvina]

Aha I just looked at my own explanation and realized it made no sense. Of course the slow one is slow for exactly the reason I expected. Sorry for the waste, but thank you for the clear complexity analysis.

Andrew Ledvina

On May 9, 2012, at 2:57 PM, "Richard O'Keefe" <ok@REDACTED> wrote:

> 
> On 10/05/2012, at 7:00 AM, Andrew Ledvina wrote:
> 
>> Okay, so I was profiling something and it led me to write this:
>> 
>> from_left(X) ->
>>   lists:foldl(fun(Y,R) -> R ++ [{Y+1,Y*2}] end, [], X).
>> 
>> from_right(X) ->
>>   lists:foldr(fun(Y,R) -> [{Y+1,Y*2}] ++ R end, [], X).
> 
> Immediate reaction:  from_left/1 is going to be atrociously slow.
> 
>> My understanding is that foldl is preferred over foldr because it is tail recursive.
> 
> ***other things being equal***
> 
> In this case, they are not.  It should be clear that from_right/1 is
> O(|X|) because it does O(1) work per element of X, while
> from_left/1 is O(|X|**2) because it does O(|R|) work per element of
> X, and R grows from empty to 2|X|-2 elements long.
> 
> Write [{Y+1,Y*2} || Y <- X] and let the compiler worry about the
> best way to do it.
> 
>> I was also to understand that putting the accumulator on the left-hand-side of the ++ operation is super bad. So, the following results were a bit of a surprise at first:
> 
> If you understood that long++short is more expensive than short++long,
> you should NOT have been surprised by your result.
> 
>