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.

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.