ex2_18.erl

%%------------------------------------------------------------------------------
%% Univ. Kent Functional Programing with Erlang
%%   Week 2: Part 18 - Consolidation: functions over lists
%%
%% Description:
%%   Optional exercises to help consolidate knowledge on defining functions
%%   over lists
%%
%% Author: Brian L. Shaver
%% Date  : 2017-03-12
%%------------------------------------------------------------------------------
-module(ex2_18).
-include_lib("eunit/include/eunit.hrl").
-export([join/2,concat/1,member/2,merge/2,split/1,mergeSort/1,quickSort/1,
         insertSort/1,permutations/1]).

%-------------------------------------------------------------------------------
% join - join two lists together like ++ operator
%   we want to use a tail recursion on the first argument and the terminal case
%   in the ideal is join([X],Ys) -> [X|Ys].
%-------------------------------------------------------------------------------
-spec join(list(),list()) -> list().
join(L,[]) ->
    L;
join([],L) ->
    L;
join([X],Ys) ->
    [X|Ys];
join([X|Xs],Ys) ->
    [X|join(Xs,Ys)].

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
join_test() ->
    ?assertEqual([],join([],[])),
    ?assertEqual([1,2],join([1],[2])),
    ?assertEqual([1,2,3,4],join([1,2,3],[4])),
    ?assertEqual([1,2,3,4,5],join([1,2],[3,4,5])).

%-------------------------------------------------------------------------------
% concat - concatenate a list of lists
-spec concat(list()) -> list().
concat([]) ->
    [];
concat([X]) ->
    X;
concat([X,Y|Xs]) ->
    join(join(X,Y),concat(Xs)).

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
concat_test() ->
    ?assertEqual([],concat([])),
    ?assertEqual("abc",concat(["abc"])),
    ?assertEqual("abcd",concat(["a","bc","d"])).

%-------------------------------------------------------------------------------
% member - test if the first argument is a member of the list
-spec member(any(),list()) -> boolean().
member(_X,[]) ->
    false;
member(X,[X|_Xs]) ->
    true;
member(X,[_Y|Ys]) ->
    member(X,Ys).

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
member_test() ->
    ?assertEqual(true,member(2,[2,0,0,1])),
    ?assertEqual(false,member(20,[2,0,0,1])),
    ?assertEqual(false,member(1,[])).

%-------------------------------------------------------------------------------
% merge - merge two sorted arrays
-spec merge(list(),list()) -> list().
merge(L,[]) ->
    L;
merge([],R) ->
    R;
merge([Lh|Ls],[Rh|_Rs]=R) when Lh < Rh ->
    [Lh|merge(Ls,R)];
merge([_Lh|_Ls]=L,[Rh|Rs]) ->
    [Rh|merge(L,Rs)].

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
merge_test() ->
    ?assertEqual([1,2,3,4],merge([2,3],[1,4])),
    ?assertEqual([1,2,3,4],merge([],[1,2,3,4])),
    ?assertEqual([1,2,3,4],merge([4],[1,2,3])).

%-------------------------------------------------------------------------------
% split/2 - splits a list into first N values and tail
%           if N > length(L) then result will just be L
%           this is using a direct recursive approach to avoid using a reverse()
%           call on the first part of the list, but I'm not sure which is more 
%           efficient.
-spec split(list(),list()) -> list().
split([],_N) ->
    [[],[]];
split([X|Xs],N) when N > 0 ->
    [L,R] = split(Xs,N-1),
    [[X|L],R];
split(X,_N) -> % N <= 0
    [[],X].

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
split1_test() ->
    ?assertEqual([[1,2,3,4],[]],split([1,2,3,4],5)),
    ?assertEqual([[1,2],[3,4]],split([1,2,3,4],2)),
    ?assertEqual([[],[1,2,3,4]],split([1,2,3,4],0)).

%-------------------------------------------------------------------------------
% split - split a list into approximately equal parts, the longer part will
%         be the first list returned.
-spec split(list()) -> list().
split(L) ->
    split(L,length(L)/2).

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
split2_test() ->
    ?assertEqual([[],[]],split([])),
    ?assertEqual([[1],[]],split([1])),
    ?assertEqual([[1,2],[3,4]],split([1,2,3,4])),
    ?assertEqual([[1,2,3],[4,5]],split([1,2,3,4,5])).

%-------------------------------------------------------------------------------
% mergeSort - implement the mergeSort algorithm
%             we need two terminal recursive conditions for this approach
%             because our split/1 method will make it look like a single value
%             list can be further divided.
-spec mergeSort(list()) -> list().
mergeSort([]) ->
    [];
mergeSort([X]) ->
    [X];
mergeSort(L) ->
    [L1,R1] = split(L),
    merge(mergeSort(L1),mergeSort(R1)).

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
mergeSort_test() ->
    ?assertEqual([],mergeSort([])),
    ?assertEqual([1],mergeSort([1])),
    ?assertEqual([1,2,3,4],mergeSort([4,1,3,2])).

%-------------------------------------------------------------------------------
% pivot - divide a list into two pieces depending on whether each element is
%         smaller or larger than an indicated pivot value.
%
% NOTE:   Because of how we're going to use this function to recurse on the
%         "left side", we need the equality to result in the value being
%         included on the Right result.
-spec pivot(list(),any()) -> list().
pivot([],_X) ->
    [[],[]];
pivot([Y|Ys],X) ->
    [L,R] = pivot(Ys,X),
    case X > Y of
       true ->
            [[Y|L],R];
        false ->
            [L,[Y|R]]
    end.

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
pivot_test() ->
    ?assertEqual([[],[]],pivot([],3)),
    ?assertEqual([[1,2],[]],pivot([1,2],3)),
    ?assertEqual([[1,2],[3,4]],pivot([1,2,3,4],3)),
    ?assertEqual([[],[2,3]],pivot([2,3],1)),
    ?assertEqual([[1,3,2],[4]],pivot([4,1,3,2],4)).

%-------------------------------------------------------------------------------
% quickSort - split the list into two according to whether items in the list
%             are larger or smaller than the pivot
-spec quickSort(list()) -> list().
quickSort([]) ->
    [];
quickSort([X]) ->
    [X];
quickSort([X|Xs]) ->
    [L1,R1] = pivot(Xs,X),
    join(quickSort(L1),[X|quickSort(R1)]).


%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
quickSort_test() ->
    ?assertEqual([],quickSort([])),
    ?assertEqual([1],quickSort([1])),
    ?assertEqual([2,2,2,2],quickSort([2,2,2,2])),
    ?assertEqual([1,2,3,4],quickSort([4,1,3,2])).

%-------------------------------------------------------------------------------
% insertSort - impelement an insertion sort method
%   For this implementation, I'm going to reuse the pivot/1 function developed 
%   with the quickSort/1 algorithm to split the tail sorted result at the value
%   of the head element, and the use the join/1 method to put together them
%   two sorted lists with the head placed as the head of the Right pivot/1 
%   result.
-spec insertSort(list()) -> list().
insertSort([]) ->
    [];
insertSort([X]) ->
    [X];
insertSort([X|Xs]) ->
    [L,R] = pivot(insertSort(Xs),X),
    join(L,[X|R]).

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
insertSort_test() ->
    ?assertEqual([],insertSort([])),
    ?assertEqual([1],insertSort([1])),
    ?assertEqual([1,2,3,4],insertSort([4,1,3,2])).

%-------------------------------------------------------------------------------
% topper - add an element to the head of each of a list of lists
-spec topper(any(),list()) -> list().
topper(_Y,[]) ->
    [];
topper(Y,[L1]) ->
    [[Y|L1]];
topper(Y,[L1|Ls]) ->
    [[Y|L1]|topper(Y,Ls)].

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
topper_test() ->
    ?assertEqual([],topper(1,[])),
    ?assertEqual([[1,2],[1,3]],topper(1,[[2],[3]])).

%-------------------------------------------------------------------------------
% inject - inject a given value into each position of a list, return the
%          resulting list of lists.
-spec inject(any(),list()) -> list().
inject(X,[]) ->
    [[X]];
inject(X,[Y|Ys]=L) ->
    [[X|L]|topper(Y,inject(X,Ys))].

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
inject_test() ->
    ?assertEqual([[1]],inject(1,[])),
    ?assertEqual([[1,2],[2,1]],inject(1,[2])),
    ?assertEqual([[1,2,3],[2,1,3],[2,3,1]],inject(1,[2,3])).

%-------------------------------------------------------------------------------
% injectAll - apply the inject function to each list in the list of lists
-spec injectAll(any(),list()) -> list().
injectAll(_X,[]) ->
    [];
injectAll(X,[L1|Ls]) ->
    join(inject(X,L1),injectAll(X,Ls)).

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
injectAll_test() ->
    ?assertEqual([],injectAll(1,[])),
    ?assertEqual([[1,2],[2,1],[1,3],[3,1]],injectAll(1,[[2],[3]])).

%-------------------------------------------------------------------------------
% permutations - simple but inefficient approach, inject the head value into
%     the permutations of the tail.
-spec permutations(list()) -> list().
permutations([]) ->
    [[]];
permutations([X|Xs]) ->
    injectAll(X,permutations(Xs)).

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
permutations_test() ->
    ?assertEqual([[]],permutations([])),
    ?assertEqual([[1]],permutations([1])),
    ?assertEqual([[1,2],[2,1]],permutations([1,2])),
    % NOTE: the order of my permutations is different than indicated in the
    %       exercise notes, but I consider this to be acceptable.
    % [[1,2,3],[2,3,1],[3,1,2],[2,1,3],[1,3,2],[3,2,1]]
    ?assertEqual([[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]],
        permutations([1,2,3])).