Writing Join in Erlang

Earlier today I found myself needing to join something in Erlang, and after spending a few minutes looking around for a join function in the lists module, realized that there wasn't one. Raising the question, how does one implement join?

The simplest way to implement join is to use a reduce/fold. Erlang provides these in lists:foldl and lists:foldr, which fold to the left and right respectively. I chose to fold from the left, and thus my function used for the fold looked like this:

% Char is assumed to exist.
JoinFunction = fun(Element, Acc) -> lists:append([Acc, Char, Element]) end.

Then we'll apply it to a list.

% List is assumed to exist.
InitialAcc = "",
Results = lists:foldl(JoinFunction, InitialAcc, List).

Now its pretty much working, but we still have a slight problem: it will be preceded by an extra copy of the joining list (for example joining ["one", "two", "three"] using ", " would look like ", one, two, three"). Fortunately, we are dealing with linked lists, so chopping off that extra copy is a O(c) operation (where c is the number of elements in the joining list).

Throw in some protection against an empty list as the list of elements to join, and we end up with a pretty simple solution.

simple_join(_, []) ->
    "";
simple_join(Char, List) ->
    P = fun(Elem, AccIn) -> lists:append([AccIn, Char, Elem]) end,
    lists:nthtail(length(Char), lists:foldl(P, "", List)).

I'm pretty content with that solution, but it felt like it would be worth throwing together a solution without using fold.

There are three situations that need to be handled by the solution.

1. Is this the first element? If so, then recurse with the accumulated list equal to list[0], and the list of elements to process equal to list[1:].
2. Are there no remaining elements? If so, return the accumulated list.
3. Else, recursively call the function on list[1:], and append the joining character and list[0] to the accumulated list.

Although not particularly concise by the number of lines metric, I find the Erlang solution to be quite pleasing.

simple_join(Char, List) ->
    simple_join(Char, List, []).
simple_join(_, [], Acc) ->
    Acc;
simple_join(Char, [First|Rest], []) ->
    simple_join(Char, Rest, First);
simple_join(Char, [First|Rest], Acc) ->
    simple_join(Char, Rest, lists:append([Acc, Char, First])).

My favorite part is that all of the logic is handled by pattern matching against function definitions, instead of handled by explicit case or if/else constructions. As far as readability goes, I think its worth comparing it to a roughly equivalent¹ function in Scheme.

(define (simple-join char list)
  (define (sj char list acc)
    (cond ((null? acc) (sj char (cdr list) (car list)))
	  ((null? (cdr list)) acc)
	  (else (sj char (cdr list) (append acc char (car list))))))
  (sj char list (list)))

Looking at the two, I think the Erlang implementation suffers because most programmers (me being no exception) are more familiar with the if-else paradigm than with pattern matching. However, I find the Erlang solution less cluttered, and easier to parse. All in all, I prefer the Erlang solution now that I have become a bit familiar with Erlang and its concepts.