ex2_9.erl

%%------------------------------------------------------------------------------
%% Univ. Kent Functional Programing with Erlang
%%   Week 2: Part 9 - Constructing Functions on Lists
%%
%% Description:
%%    Familiarize yourself with other ways of defining functions over lists
%%
%% Author: Brian L. Shaver
%% Date  : 2017-03-10
%%------------------------------------------------------------------------------
-module(ex2_9).
-include_lib("eunit/include/eunit.hrl").
-export([reverse/1,merge/2,mergeSort/1,double/1,evens/1,evens2/1,evensTR/1,
         divide/1,median/1,modes/1]).

%-------------------------------------------------------------------------------
% reverse - reverse the contents of a list.
%   This comes in handy because when we construct lists as [X|Xs], then 
%   we frequently construct lists in the opposite order we'd like them to end
%   in.
reverse(L) ->
    reverse([],L).

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

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

%-------------------------------------------------------------------------------
% divide - divides a list in half
%   when the list has an odd number of elements, the longer side of the lists
%   will be the left half. this is so the case of a single element list will
%   be in the first list of the result. 
%
%   For example: [[1],[]] = divide([1])
%
divide([]) ->
    [[],[]];
divide(L) ->
    divide(L,[],length(L)/2,0).

divide([X|Xs],A,H,I) when I < H ->
    divide(Xs,[X|A],H,I+1);
divide(Xs,A,_,_) ->
    [reverse(A),Xs].

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

%-------------------------------------------------------------------------------
% merge - merge two sorted arrays together
%  the results for unsorted arrays are not specified.
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([],merge([],[])),
    ?assertEqual([1,2,3,4],merge([1,2],[3,4])),
    ?assertEqual([1,2,3,4,5],merge([1,2,3,4],[5])),
    ?assertEqual([1,2,3,4,5],merge([3,5],[1,2,4])).


%-------------------------------------------------------------------------------
% mergeSort - basic divide and conquer sorting, works well as recursive
%   list processing function. 
%
%  NOTE: in order to properly terminate the recursion, we need to handle 
%     terminating for both [] and [X] single element lists because if we 
%     another level of mergeSort() on single element lists, it creates infinite
%     recursion due to divide([1]) == [[1],[]] % which then soreted recursively
mergeSort([]) ->
    [];
mergeSort([X]) ->
    [X];
mergeSort(L) ->
    [L1,R1] = divide(L),
    merge(mergeSort(L1),mergeSort(R1)).

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


%-------------------------------------------------------------------------------
% double - double each element of a lists
double([]) ->
    [];
double([X|Xs]) ->
    [2*X|double(Xs)].

%++++++++++++++++++++++++++++++++++++++++
% unit tests
%++++++++++++++++++++++++++++++++++++++++
double_test() ->
    ?assertEqual([],double([])),
    ?assertEqual([2,4,6],double([1,2,3])),
    ?assertEqual([6,4,2],double([3,2,1])).

%-------------------------------------------------------------------------------
% evens - filter the even numbers from a list
evens([]) ->
    [];
evens([X|Xs]) when X rem 2 == 0 ->
    [X|evens(Xs)];
evens([_X|Xs]) ->
    evens(Xs).


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

%-------------------------------------------------------------------------------
evens2([]) ->
    [];
evens2([X|Xs]) ->
    case X rem 2 of
        0 ->
            [X|evens(Xs)];
        _ ->
            evens(Xs)
    end.

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

%-------------------------------------------------------------------------------
evensTR(L) ->
    evensTR([],L).

evensTR(R,[]) ->
    reverse(R);
evensTR(R,[X|Xs]) when X rem 2 == 0 ->
    evensTR([X|R],Xs);
evensTR(R,[_X|Xs]) ->
    evensTR(R,Xs).

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

%-------------------------------------------------------------------------------
% median - the middle value in the list
%   I'm using the mergeSort/1 to give me a sorted list and then the divide/1
%   method to split the list in half (L and R). Based on the length of the 
%   list, then either I'm going to need the very last element of the L(eft) 
%   split of the list, or I'm going to need to average the L(eft) last element
%   with the hd(R)ight list.
%
%  OPTIMIZE: In order to get at the last element of a list, I'm using 
%     reverse/1 and hd(). It seems like this would be inefficient.
median(X) ->
    Lsort = mergeSort(X),
    [L,R] = divide(Lsort),
    N = length(Lsort),
    case N of
       _N when N rem 2 == 0 ->
            (hd(R) + hd(reverse(L)))/2;
       _N ->
            hd(reverse(L))
    end.

median_test() ->
    ?assertEqual(1.5,median([1,2])),
    ?assertEqual(2,median([1,2,3])),
    ?assertEqual(6.0,median([1,4,8,9])).

%-------------------------------------------------------------------------------
% modes - numbers which occur most frequently
%   We're going to sort the array and then walk through it as now any value
%   which occurs multiple times must occur in order. As we walk through it 
%   we need to keep track of: 
%      A - current modes list answer
%      M - the maximum occurence count we've found so far
%      C - how many times we've seen the element at the head of the list last
%      X - the value we're tracking
%
%  then there are two cases to consider:
%     either we're seeing the same value again X matches hd() of the list
%     OR we're seeing a new value. 
%         when we see a new value, there is a special case when M == 1 because
%         in that case ... every new value we encounter will be added to there
%         modes answer.
modes([]) ->
    [];
modes(L) ->
    [X|Xs] = mergeSort(L),
    modes(Xs,[X],1,1,X).

modes([],A,_,_,_) ->
    mergeSort(A); % return the results sorted for predictability
modes([X|Xs],A,M,C,X) ->
    case C of
        _C when C+1 == M ->
            modes(Xs,[X|A],M,M,X);
        _C when C+1 > M->
            modes(Xs,[X],C+1,C+1,X);
        _C when C+1 < M ->
            modes(Xs,A,M,C+1,X)
    end;
modes([Y|Xs],A,M,_C,_X) ->
    case M of
        _M when M == 1 ->
            modes(Xs,[Y|A],M,1,Y);
        _M ->
            modes(Xs,A,M,1,Y)
    end.

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