[erlang-questions] foldl vs foldr and ++

[Paweł Peregud]

As I see it, cost of being not tail-recursive is O(2n) comparing to O(n)
for tail-recursive where n is the number of calls. Cost of from_left in
your example is O(n^2), because for every element whole linked list is
reconstructed.
On May 9, 2012 11:58 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20120510/c59e2d92/attachment.htm>