main.erl

-module(main).
-export([join/2, concat/1, member/2,
  merge_sort/1, qsort/1, insertion_sort/1,
  perms/1]).

shunt([],Xs) ->
    Xs;
shunt([X|Xs],Ys) ->
    shunt(Xs,[X|Ys]).

reverse(Xs) ->
    shunt(Xs,[]).

join(Xs, Ys) ->
  shunt(reverse(Xs), Ys).

concat([]) -> [];
concat([List]) -> List;
concat([List1, List2|Tail]) ->
  concat([join(List1, List2)|Tail]).

member(_, []) -> false;
member(X, [X|_]) -> true;
member(X, [_|Xs]) ->
  member(X, Xs).

partition(Pred, List) ->
  partition(Pred, List, {[], []}).

partition(_, [], {Left, Right}) ->
  {reverse(Left), reverse(Right)};
partition(Pred, [X|Xs], {Left, Right}) ->
  case Pred(X) of
    true -> partition(Pred, Xs, {[X|Left], Right});
    false -> partition(Pred, Xs, {Left, [X|Right]})
  end.

split(0, {Left, Right}) ->
  {reverse(Left), Right};
split(_, {Left, []}) ->
  {reverse(Left), []};
split(N, {Left, [X|Xs]}) ->
  split(N-1, {[X|Left], Xs});

split(N, List) ->
  split(N, {[], List}).

zip_join([], Ys) -> Ys;
zip_join(Xs, []) -> Xs;
zip_join([X|Xs] = List1, [Y|Ys] = List2) ->
  case X < Y of
    true -> [X|zip_join(Xs, List2)];
    false -> [Y|zip_join(List1,Ys)]
  end.

merge_sort([]) -> [];
merge_sort([X]) -> [X];
merge_sort(List) ->
  {Left, Right} = split(length(List) div 2, List),
  zip_join(merge_sort(Left), merge_sort(Right)).

qsort([]) -> [];
qsort([X|Xs]) ->
  {Left, Right} = partition(fun (Y) -> Y < X end, Xs),
  concat([qsort(Left), [X], qsort(Right)]).

insert(X, []) -> [X];
insert(X, [Y|Ys] = Sorted) ->
  case X < Y of
    true -> [X|Sorted];
    false -> [Y|insert(X, Ys)]
  end.

insertion_sort(Sorted, []) -> Sorted;
insertion_sort(Sorted, [X|Xs]) ->
  insertion_sort(insert(X, Sorted), Xs).
insertion_sort(List) -> insertion_sort([], List).

insert_after(Index, X, List) ->
  {Left, Right} = split(Index, List),
  concat([Left, [X], Right]).
insert_all(X, 0, List) ->
  [[X|List]];
insert_all(X, N, List) ->
  [insert_after(N, X, List)|insert_all(X, N-1, List)].

map(_, []) -> [];
map(Pred, [X|Xs]) ->
  [Pred(X)|map(Pred, Xs)].

perms([]) -> [];
perms([X]) -> [[X]];
perms([X|Xs]) ->
  Perms = map(fun (Ys) -> insert_all(X, length(Ys), Ys) end, perms(Xs)),
  concat(Perms).

main_test.erl

-module(main_test).
-export([test/0]).
-import(main, [join/2, concat/1, member/2,
  merge_sort/1, qsort/1, insertion_sort/1,
  perms/1]).

test_join() ->
  [] = join([], []),
  [1,2] = join([1], [2]).

test_concat() ->
  [1,2,3] = concat([[1], [2], [3]]).

test_member() ->
  false = member(1, []),
  true = member(2, [1,2]).

test_sort() ->
  Unsorted = [8,0,5,6,4],
  Sorted = [0,4,5,6,8],
  [] = merge_sort([]),
  [] = qsort([]),
  [] = insertion_sort([]),
  Sorted = merge_sort(Unsorted),
  Sorted = qsort(Unsorted),
  Sorted = insertion_sort(Unsorted).

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

test() ->
  test_join(),
  test_concat(),
  test_member(),
  test_sort(),
  test_perms(),
  ok.