[erlang-questions] foldl vs foldr and ++

[Andrew Ledvina]

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).

 timeit(N) ->
   X = lists:seq(1,N),
   statistics(runtime),
   statistics(wall_clock),
   from_left(X),
   {_,LTime1} = statistics(runtime),
   {_,LTime2} = statistics(wall_clock),
   from_right(X),
   {_,RTime1} = statistics(runtime),
   {_,RTime2} = statistics(wall_clock),
   io:format("Left  runtime: ~p (~p)~n", [LTime1,LTime2]),
   io:format("Right runtime: ~p (~p)~n", [RTime1,RTime2]).

My understanding is that foldl is preferred over foldr because it is tail
recursive. 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:

 Erlang R14B01 (erts-5.8.2) [source] [smp:4:4] [rq:4] [async-threads:0]
[hipe] [kernel-poll:false]

 Eshell V5.8.2  (abort with ^G)
 1> listtime:timeit(10000).
 Left  runtime: 290 (286)
 Right runtime: 0 (1)
 ok
 2> listtime:timeit(100000).
 Left  runtime: 30670 (31011)
 Right runtime: 10 (13)
 ok

The times are in ms. 30 s versus 10 ms. The result of both functions
from_left and from_right are identical. Also, I am clearly aware that these
are both equivalent to just a more simple map. I think I understand the
results after a bit of a go around but is there anyone who has a simple,
clear explanation?

--Andrew Ledvina
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20120509/4fd77be3/attachment.htm>