How can I write Erlang's list concatenate without using the lists module?

Question

The book I'm reading about Erlang has exercises in the back of it and one is to re-create the lists:append function.

I could do this simply using the ++ operator, but isn't this really slow? And I think the point of the exercise is to do it using list operations that I write.

So far the only approach that I could think of is to do something like:

concat([], _, Results)->
  Results;
concat(_, [], Results)->
  Results;
concat([Ah|At],B,Results) ->
  concat(At,B,[Ah|Results]).

But I know this is incorrect...

Any suggestions on how to go about doing this?

EDIT: To clarify the question, here is an example input and output:

Input: [[1,2,3],[],[4,5],[6]] Output: [1,2,3,4,5,6]

After working a while, I came up with this code as well:

append([A|[B|[T|[]]]]) ->
  append([A++B|T]);
append([H|T]) ->
  H++T.

However, this only works for when the list is size 3. How can I modify this so that it works for any given amount of randomly sized lists?

Answer 1

++ is only slow when used wrongly, used carefully it is as fast as anything you could craft by hand. You have to make sure you work through the list in the correct direction, otherwise the resulting append is O(N^2). When we do X ++ Y, we must make a copy of X and then prepend it to Y which is not copied.

In this function, the accumulator appears on the left hand side of the ++, so the append is not efficient.

concatl(Lst) ->
    concatl(Lst, []).
concatl([], Acc) ->
    Acc;
concatl([H|T], Acc) ->
    concatl(T, Acc ++ H).

This function performs much better, even though it's not tail recursive.

concat([]) -> [];
concat([H|T]) ->
    H ++ concat(T).

In this case rewriting to be tail recursive is only a modest improvement:

concat2(Lst) ->
    concat2(lists:reverse(Lst), []).
concat2([], Acc) -> Acc;
concat2([H|T], Acc) ->
    concat2(T, H ++ Acc).

The timings on a big input list show just how huge the improvement is. (Times are in microseconds.)

41> Time(fun() -> test:concatl([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
14539061
40> Time(fun() -> test:concat([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
245356
42> Time(fun() -> test:concat2([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
211571

Answer 2

You only need two parameters to your concat function, as you'll be appending to one of the parameters and that's what you'll eventually return. Something like (untested):

concat(L,[]) ->
   L;
concat(L,[H|T]) ->
   concat(L ++ [H],T).

The ++ is the append operator, you're going to have to do that to be efficient.

(The idea of the above is to return the left parameter if we've no more left, or call again after moving one of the elements from the right to the left). There's probably more efficiencies around doing the append in reverse and then finally reversing the answer but hey...)

(Just saw your edit, and mine of course only works for two things to append, but you can recurse through the above function for each element in your list of lists...)