<p>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.</p>

<div class="gmail_quote">On May 9, 2012 11:58 PM, "Richard O'Keefe" <<a href="mailto:ok@cs.otago.ac.nz">ok@cs.otago.ac.nz</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
On 10/05/2012, at 7:00 AM, Andrew Ledvina wrote:<br>
<br>
> Okay, so I was profiling something and it led me to write this:<br>
><br>
>  from_left(X) -><br>
>    lists:foldl(fun(Y,R) -> R ++ [{Y+1,Y*2}] end, [], X).<br>
><br>
>  from_right(X) -><br>
>    lists:foldr(fun(Y,R) -> [{Y+1,Y*2}] ++ R end, [], X).<br>
<br>
Immediate reaction:  from_left/1 is going to be atrociously slow.<br>
<br>
> My understanding is that foldl is preferred over foldr because it is tail recursive.<br>
<br>
***other things being equal***<br>
<br>
In this case, they are not.  It should be clear that from_right/1 is<br>
O(|X|) because it does O(1) work per element of X, while<br>
from_left/1 is O(|X|**2) because it does O(|R|) work per element of<br>
X, and R grows from empty to 2|X|-2 elements long.<br>
<br>
Write [{Y+1,Y*2} || Y <- X] and let the compiler worry about the<br>
best way to do it.<br>
<br>
> 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:<br>
<br>
If you understood that long++short is more expensive than short++long,<br>
you should NOT have been surprised by your result.<br>
<br>
<br>
_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
</blockquote></div>