[erlang-questions] foldl vs foldr and ++

[Robert Virding]

The documentation is referring to the *implementation* of the foldl/foldr functions, foldl uses a tail-recursive function while foldr cannot do that. The difference in speed comes from what you do inside the fold function. As others have pointed out the efficiency of ++ depends solely on its left argument.

Robert

----- Original Message -----
> 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.
> > 
> > 
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>