[erlang-questions] foldl vs foldr and ++

[Richard O'Keefe]

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.