FutureLearn — Functional Programming in Erlang — Week 2

mwpastore_week2.erl

-module(mwpastore_week2).
-export([
  shunt/2, reverse/1,
  join/2, concat/1,
  member/2,
  msort/1, qsort/1, isort/1,
  perms/1
]).

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

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

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

concat(Xs) -> concat(Xs, []).

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

member(_, []) -> false;
member(X, [Y|_]) when X == Y -> true;
member(X, [_|Ys]) -> member(X, Ys).

msort([]) -> [];
msort([X]) -> [X];
msort(Xs) ->
  {As, Bs} = lists:split(length(Xs) div 2, Xs),
  reverse(merge(msort(As), msort(Bs), [])).

merge([], [], Cs) -> Cs;
merge(As, [], Cs) -> shunt(As, Cs);
merge([], Bs, Cs) -> shunt(Bs, Cs);
merge([A|As]=Xs, [B|Bs]=Ys, Cs) ->
  if
    A == B -> merge(As, Bs, [A, B|Cs]);
    A <  B -> merge(As, Ys, [A|Cs]);
    A  > B -> merge(Xs, Bs, [B|Cs])
  end.

qsort([]) -> [];
qsort([X]) -> [X];
qsort([X|Xs]) ->
  {As, Bs} = lists:partition(fun(Y) -> X > Y end, Xs),
  join(qsort(As), [X|qsort(Bs)]).

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

insert(X, [], Zs) -> [X|Zs];
insert(X, [Y|Ys], Zs) when X < Y ->
  shunt(Ys, [Y, X|Zs]);
insert(X, [Y|Ys], Zs) ->
  insert(X, Ys, [Y|Zs]).

perms(Xs) -> perms(length(Xs), Xs).

perms(_, []) -> [[]]; % stop condition for permute down
perms(0, _) -> []; % stop condition for permute across
perms(N, [X|Xs]) ->
  As = perms(length(Xs), Xs), % permute down (i.e. into subset)
  Bs = perms(N - 1, join(Xs, [X])), % rotate and permute across
  join(prepend(X, As, []), Bs).

% insert X into every Xs at position zero
prepend(_, [], Ys) -> Ys;
prepend(X, [Xs|Xss], Ys) -> prepend(X, Xss, [[X|Xs]|Ys]).