FutureLearn - Functional Programming in Erlang 2.18 - Consolidation: functions over lists

consolidations.erl

-module(consolidation).
-export([test_join/0,test_member/0,test_concat/0,
         test_isort/0,test_msort/0,test_qsort/0,
         test_perms/0,
         concat/1,perms/1,
         isort/1,msort/1,qsort/1,
         insert/2,join/2,member/2]).

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

test_join() ->
    [] = join([],[]),
    "goodbye" = join("good","bye"),
    success.

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

test_concat() ->
    "goodbye" = concat(["goo","d","","by","e"]),
    success.

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

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

%% -----------------------------------------------------------------------------
%% Merge sort
merge(Xs, []) -> Xs;
merge([], Ys) -> Ys;
merge([X|Xs], [Y|Ys]) when X < Y -> [X|merge(Xs, [Y|Ys])];
merge(Xs, [Y|Ys]) -> [Y|merge(Xs, Ys)].

-spec msort([T]) -> [T].
msort([]) -> [];
msort([X]) -> [X];
msort(Xs) ->
    {Xs1, Xs2} = lists:split(length(Xs) div 2, Xs),
    merge(msort(Xs1), msort(Xs2)).

test_msort() ->
    [1,2,3,4,5] = msort([5,2,1,4,3]),
    success.

%% -----------------------------------------------------------------------------
%% Quick sort

%% helpers for qsort
filterL(_,[]) -> [];
filterL(Pivot, [X|Xs]) when X < Pivot -> [X|filterL(Pivot,Xs)];
filterL(Pivot, [_|Xs]) -> filterL(Pivot,Xs).

filterP(_,[]) -> [];
filterP(Pivot, [X|Xs]) when X >= Pivot -> [X|filterP(Pivot,Xs)];
filterP(Pivot, [_|Xs]) -> filterP(Pivot,Xs).

-spec qsort([T]) -> [T].
qsort([]) -> [];
qsort([Pivot|Xs]) ->
    qsort(filterL(Pivot,Xs)) ++ [Pivot] ++ qsort(filterP(Pivot,Xs)).

test_qsort() ->
    [1,2,3,4,5] = qsort([5,2,1,4,3]),
    success.

%% -----------------------------------------------------------------------------
%% Insertion sort
insert(X,[]) -> [X];
insert(X, [Y|Ys]) when X < Y ->
    [X,Y|Ys];
insert(X, [Y|Ys]) ->
    [Y|insert(X,Ys)].

-spec isort([T]) -> [T].
isort(Xs) ->
    isort(Xs, []).

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

test_isort() ->
    [1,2,3,4,5] = isort([5,2,1,4,3]),
    success.

%% -----------------------------------------------------------------------------
%% Permutations (fixed-head solution: https://en.wikipedia.org/wiki/Permutation)
%% I was not able to come up with a suitable solution with basic direct 
%% recursions, so had recourse to Erlang high order functions 'lists:foldl' and
%% 'lists:map' to take care of the heavy lifting.

%% The fold starts with and empty list as accumulator. The lambda in the fold,
%% takes the current element (X) in the list and passes it to the lambda of the
%% map. The map combines each element of the list with the permutation of
%% the other elements (the lists minus the selected element). The fold combines
%% all the sub-lists into a single list to give the final result.
-spec perms([T]) -> [[T]].
perms([]) -> [];
perms([X]) -> [[X]];
perms(List) ->
    lists:foldl(fun(X, Acc) ->
        Acc ++ lists:map(fun(Y) -> [X|Y] end, perms(List--[X])) end, [], List).

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