lists2.erl

-module(lists2).
-export([join/2,concat/1,member/2,sort/1,sort/2,perms/1]).
-export([join_test/0,concat_test/0,member_test/0,sort_test/0,perms_test/0]).

%% Join %%%
join(L1, L2) when is_list(L1), is_list(L2) ->
  join_internal(lists:reverse(L1), L2).

join_internal(L1, []) -> lists:reverse(L1);
join_internal(L1, [H|T]) ->
  join_internal([H|L1], T).

join_test() ->
  [] ++ [] = join([],[]),
  [3] ++ [] = join([3], []),
  [] ++ [3] = join([], [3]),
  [] ++ [1,2,3] = join([], [1,2,3]),
  [1,2,3] ++ [] = join([1,2,3], []),
  [2] ++ [3] = join([2],[3]),
  [1,2] ++ [3,4] = join([1,2], [3,4]),
  [1,[2],[3,4],5] = join([1,[2]], [[3,4],5]),
  passed.

%% Concat %%%

concat(L) when is_list(L)->
  concat_internal(L, []).

concat_internal([], Ac) -> Ac;
concat_internal([H|T], Ac) ->
  case is_list(H) of
    true -> concat_internal(T, concat_internal(H, Ac));
    false -> concat_internal(T, join(Ac, [H]))
  end.

concat_test() ->
  [] = concat([[],[]]),
  "goodbye" = concat(["goo", "d", "", "by", "e"]),
  [1,2,3,4,5] = concat([[1], [2,3], 4, [5]]),
  [1,2,3,4,5] = concat([[1,2],3,4,5]),
  [1,2,3,4,5] = concat([1,[[2,[3]],[4]],5]),
  passed.

%% Member %%%

member(_, []) -> false;
member(A, [H|T]) ->
  case A == H of
    true -> true;
    false -> member(A, T)
  end.

member_test() ->
  true = member(2, [2,0,0,1]),
  false = member(20, [2,0,0,1]),
  true = member([2], [1,[2]]),
  % [3,4] is not a member of the given list, but a "member of a member" of that list
  false = member([3,4], [1,[2,[3,4]]]),
  passed.

%% Sort %%%

sort(L) when is_list(L) ->
  sort(L, merge).

sort(L, Method) when is_list(L) ->
  case Method of
    merge -> merge_sort(L);
    quick -> quick_sort(L);
    insert -> insert_sort(L);
    _ -> bad_method
  end.

%% Merge sort %%%

merge_sort([]) -> [];
merge_sort([H|[]]) -> [H];
merge_sort(L) when is_list(L) ->
  {L1, L2} = lists:split(length(L) div 2, L),
  merge_internal(merge_sort(L1), merge_sort(L2), []).

merge_internal([], L2, Ac) -> join(Ac, L2);
merge_internal(L1, [], Ac) -> join(Ac, L1);
merge_internal([H1|T1] = _L1, [H2|_T2] = L2, Ac) when H1<H2 ->
  merge_internal(T1, L2, join(Ac, [H1]));
merge_internal([_H1|_T1] = L1, [H2|T2] = _L2, Ac) ->
  merge_internal(T2, L1, join(Ac, [H2])).

%% Quicksort %%%

quick_sort([]) -> [];
quick_sort([H|T]) ->
  T2 = join([H], quick_sort([X || X <- T, X >= H])),
  join(quick_sort([X || X <- T, X < H]), T2).

%% Insertion sort %%%

insert_sort([]) -> [];
insert_sort(L) -> insert_sort(L, []).

insert_sort([], L) -> L;
insert_sort([H|T], L) ->
  insert_sort(T, insert(H,L)).

insert(A, []) -> [A];
insert(A, [H|_] = L) when A =< H -> [A|L];
insert(A, [H|T] = _) -> [H | insert(A, T)].

sort_test() ->
  [] = sort([]),
  [1] = sort([1]),
  [1,2,3] = sort([2,3,1]),
  [1,2,3,4,5] = sort([5,1,3,2,4]),
  [1,2,3] = sort([2,3,1], merge),
  [] = sort([], quick),
  [1] = sort([1], quick),
  [1,2,3] = sort([2,3,1], quick),
  [1,2,3,4,5] = sort([5,1,3,2,4], quick),
  [1,2,3] = sort([2,3,1], merge),
  [] = sort([], insert),
  [1] = sort([1], insert),
  [1,2,3] = sort([2,3,1], insert),
  [1,2,3,4,5] = sort([5,1,3,2,4], insert),
  bad_method = sort([], doh),
  passed.

%% Permutations %%%

perms([]) -> [[]];
perms(L) ->
  [[A|B] || A <- L, B <- perms(L--[A])].

perms_test() ->
  [[]] = perms([]),
  [[1]] = perms([1]),
  [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] = perms([1,2,3]),
  passed.

Nice coding! A few tips…

1. Let it Crash
It's generally not recommended to do defensive programming (like checking if the arguments are lists on join/2).
The idea here is that if the function is not intended to be used with things that are not lists, you can trust your fellow developers (and yourself) not to use the function with things that are not lists. And if they do try to use it with non-lists… well… the results may be unpredictable (most likely, the code will fail anyway).
If you want to be super-clear on the fact that it only should be called with lists, you add a spec…

-spec join([T1], [T2]) -> [T1 | T2].

And if you want to be very very sure that you're not accidentally calling this function with things that are not lists, you use dialyzer.
For instance, you can totally write sort/2 as…

sort(L, Method) ->
  case Method of
    merge -> merge_sort(L);
    quick -> quick_sort(L);
    insert -> insert_sort(L)
  end.

2. More pattern-matching, less case statements
You can simplify member/2 like this…

member(_, []) -> false;
member(A, [A|T]) -> true;
member(A, [_|T]) -> member(A, T).

…and concat_internal/2 like this…

concat_internal([], Ac) -> Ac;
concat_internal([H|T], Ac) when is_list(H) -> concat_internal(T, concat_internal(H, Ac));
concat_internal([H|T], Ac) -> concat_internal(T, join(Ac, [H])).

(besides, why don't you use join(H, Ac) instead of concat_internal(H, Ac) on that second clause?)
…and, of course, you can write sort/2 like…

sort(L, merge) -> merge_sort(L);
sort(L, quick) -> quick_sort(L);
sort(L, insert) -> insert_sort(L).

3. list-comprehensions
Using list-comprehensions for quick sort is a little bit of cheating
You're using your own functions everywhere, you should've defined larger_than(X, [X]) -> [X] and smaller_than(X, [X]) -> [X] 😉

That is an awesome review. Thank you so much! :)

That solution for perms is so clean. I had the base case and then started to flounder at once. Just going round in circles and making no progress.