Week 2 - More functions over lists

more_functions_over_lists.erl

-module(more_functions_over_lists).

-export([join/2, concat/1]).
-export([reverse/1]).
-export([member/2]).
-export([merge_sort/1, quick_sort/1, insertion_sort/1]).
-export([permutations/1]).

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

concat([]) -> [];
concat([X | Xs]) ->
  join(X, concat(Xs)).

reverse(Xs) -> reverse(Xs, []).
reverse([], Result) -> Result;
reverse([X | Xs], Result) ->
  reverse(Xs, [X | Result]).

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

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

merge_sort([]) -> [];
merge_sort([X]) -> [X];
merge_sort(Xs) ->
  {L, R} = split(length(Xs) div 2, Xs),
  merge(merge_sort(L), merge_sort(R)).

merge(Xs, Ys) -> merge(Xs, Ys, []).
merge([], [], Result) -> reverse(Result);
merge([], Right, Result) -> join(reverse(Result), Right);
merge(Left, [], Result) -> join(reverse(Result), Left);
merge([X | Xs] = Left, [Y | Ys] = Right, Result) ->
  case X =< Y of
    true -> merge(Xs, Right, [X | Result]);
    false -> merge(Left, Ys, [Y | Result])
  end.

quick_sort([]) -> [];
quick_sort([Pivot | Xs]) ->
  quick_sort([X || X <- Xs, X < Pivot]) ++
  [Pivot] ++
  quick_sort([X || X <- Xs, X >= Pivot]).

insertion_sort(L) -> lists:foldl(fun insert/2, [], L).

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

permutations([]) -> [[]];
permutations(L) ->
  [[X | Y] || X <- L, Y <- permutations(L -- [X])].