-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).