I was reading Learn You Some Erlang and I came upon this example in the Recursion chapter.
tail_sublist(_, 0, SubList) -> SubList;
tail_sublist([], _, SubList) -> SubList;
tail_sublist([H|T], N, SubList) when N > 0 ->
tail_sublist(T, N-1, [H|SubList]).
As the author goes on to explain that there is a fatal flaw in our code. It being that the sub lists hence produced would be reverse and we would have to re-reverse them to get the correct output. In contrast, what I did was use the ++ operator to avoid reversing the list later.
sublist_tail([],_,Acc) -> Acc;
sublist_tail(_,0,Acc) -> Acc;
sublist_tail([H|T],N,Acc) -> sublist_tail(T,N-1,Acc++[H]).
My question is, is the ++ operator more expensive than the | operator? And if it is, would my solution (using ++ operator) still be slow compared to the author's solution (including reversing the list to get the correct output)?
is the ++ operator more expensive than the | operator?
That depends. If you use it correctly, then no. ++ is only dangerous when you have a big left-hand-side operand.
Each time a "++"-operator is invoked on a left-hand List (like: List1 ++ List2), you are creating a new List, that is a copy of your left-hand operand (List1). Each copy operation then has a runtime, that is dependent on the length of your List1 (which keeps growing with your iterations).
So, if you prepend your values 'head first', you don't have to perform a copy-operation over the whole list in each step. This also means, accumulation with ++ at the head of the List wouldn't be so bad either, since only the "H"-value is copied once in each iteration:
sublist_tail([H|T],N,Acc) -> sublist_tail(T,N-1,[H]++Acc).
But if you are already accumulating head-first (and thus have to reverse later anyhow), you can do it with the cons-operator (|)
sublist_tail([H|T],N,Acc) -> sublist_tail(T,N-1,[H|Acc]).
This is the 'proper' way, since (please correct me if I am wrong) ++ is only syntactic sugar and is implemented internally with a cons-operator (|).
You might want to read about this issue in the Erlang efficiency guide, since there it says that building the list via | and then reversing the result is more efficient than using the appending ++ operator. If you want to know the performance difference, use timer:tc:
1> timer:tc(fun() -> lists:reverse(lists:foldl(fun(V, Acc) -> [V|Acc] end, [], lists:seq(1,1000))) end).
{1627,
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
23,24,25,26,27|...]}
2> timer:tc(fun() -> lists:foldl(fun(V, Acc) -> Acc++[V] end, [], lists:seq(1,1000)) end).
{6216,
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
23,24,25,26,27|...]}
Both approaches create lists of 1000 integers, but these measurements based on Erlang/OTP 17.5 show the prepending/reversing version is roughly 4x faster than the appending version (YMMV of course).
