Functions over lists

x.erl

-module(x).
-compile(export_all).
-include_lib("eunit/include/eunit.hrl").

evens_test() ->
    [] = evens([]),
    [-2, 0, 2] = evens([-2, -1, 0, 1, 2]),
    [4, 2, 0] = evens([4, 3, 2, 1, 0]),
    all_tests_passed.

evens([]) -> [];
evens(L) -> evens(L, []).

evens([X|Xs], Acc) when X rem 2 =:= 0 ->
    evens(Xs, [X|Acc]);
evens([X|Xs], Acc) when abs(X rem 2) =:= 1 -> % -3 rem 2 => -1
    evens(Xs, Acc);
evens([], Acc) ->
    reverse(Acc).

%---------------

reverse_test() ->
    [] = reverse([]),
    [2, 1] = reverse([1, 2]),
    [1, 2, 3] = reverse([3, 2, 1]),
    all_tests_passed.

reverse([]) -> [];
reverse(L) -> reverse(L, []).

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

double_test() ->
    [] = double([]),
    [2, 4] = double([1, 2]),
    [-4, 4] = double([-2, 2]),
    [-2, 0, 2, 4, 6] = double([-1, 0, 1, 2, 3]),
    all_tests_passed.

double(L) -> double(L, []).

double([X|Xs], Acc) ->
    double(Xs, [X*2|Acc]);
double([], Acc) ->
    reverse(Acc).

%---------

contains(_, []) ->
    false;
contains(N, [N|_]) ->
    true;
contains(N, [_|Xs]) ->
    contains(N, Xs).

nub(L) -> nub(L, []).

nub([], Acc) ->
    lists:reverse(Acc);
nub([X|Xs], Acc) -> 
   case contains(X, Acc) of
      true  -> nub(Xs, Acc);
      false -> nub(Xs, [X|Acc])
   end.

%-------------

mysort_test() ->
    [] = mysort([]),
    [1] = mysort([1]),
    [-1,0,1] = mysort([0,1,-1]),
    [1,2,3,4] = mysort([4,3,1,2]),
    [1,1,3,3,3,3] = mysort([3,3,1,3,1,3]),
    [1,3,3,3,3,3] = mysort([1,3,3,3,3,3]),
    [-2,-2,-2,-1,0,1,2,3,3] = mysort([-1,3,0,-2,-2,-2,3,2,1]),
    all_tests_passed.

mysort(L) ->
    Sorted = mysort(L, []),
    sort_more(Sorted, L).

sort_more(Sorted, L) when Sorted =:= L -> %If nothing chaged after a sort, then done.
    Sorted;
sort_more(Sorted, _L) ->  %Otherwise, keep sorting.
    mysort(Sorted).

mysort([], Acc) ->
    reverse(Acc);
mysort([X1], Acc) ->
    reverse([X1|Acc]);
mysort(L, Acc) ->
    {NewL, NewAcc} = advance_big(L, Acc),
    mysort(NewL, NewAcc).

advance_big([X1,X2|Xs], Acc) when X1 >= X2 -> 
    {[X1|Xs], [X2|Acc]};
advance_big([X1,X2|Xs], Acc) when X1 < X2 ->
    {[X2|Xs], [X1|Acc]}.

%-------------------

median_test() ->
    1 = median([1]),
    1.5 = median([1, 2]),
    0 = median([-1, 0, 1]),
    3 = round(median([1, 3, 3, 3])),
    all_tests_passed.

median(L) ->
    Sorted = mysort(L),
    median(L, len(Sorted)).

median(L, Len) when Len rem 2 =:= 1 ->
    {_, M2} = middle(Len div 2, L),   %Get middle value when even length list
    M2;
median(L, Len) ->
    {M1, M2} = middle(Len div 2, L),  %Get middle value when odd length list
    (M1 + M2)/2.


middle_test() ->
    {none, 4} = middle(0, [4]),
    {-1, 0} = middle(1, [-1, 0]),
    {2, 4} = middle(1, [2,4,5]),
    {0, 4} = middle(2, [-1, 0, 4, 2]),
    all_tests_passed.
    
    
middle(_, [X]) -> {none, X}; %For one element list, return the element.
middle(Index, L) ->  
    Pos = 1,
    middle(Index, L, Pos).

%middle() returns the two middle elements for all lists:
%   odd length lists  => middle is X2. 
%   even length lists => middle is (X1+X2)/2.
middle(Index, [X1,X2|_], Index) ->
    {X1, X2};  
middle(Index, [_|Xs], Pos) -> 
    middle(Index, Xs, Pos+1).

len_test() ->
    0 = len([]),
    1 = len([-1]),
    2 = len([0, -1]),
    3 = len([1, -1, 0]),
    all_tests_passed.

len(L) ->
    len(L, 0).

len([], Count) ->
    Count;
len([_|Xs], Count) ->
    len(Xs, Count+1).

%--------------

count_test() ->
    0 = count(3, []),
    1 = count(-1, [1, -1, 2]),
    2 = count(0, [1, 0, -1, 0, -2, -1]),
    3 = count(1, [1, 0, 1, 3, 1]),
    4 = count(1, [1, 1, 1, 1]),
    all_tests_passed.

extract_results_test() ->
    [] = extract_results([
            {2, 1},  %{Number, Count}
            {3, 1}
        ]),

    [2] = extract_results([ 
            {2, 3} 
          ]),

    [-1, 1] = lists:sort(
          extract_results([
              {-1, 3},
              {1, 3}
          ])
    ),
    all_tests_passed.

mode2_test() ->
    [-1] = mode2([-1, 0, -1, 1]),
    [2, 3] = mode2([2, 0, 3, 2, -1, 3]),
    [] = mode2([0, -1, 1, -2, 2]),
    [1, 2, 3] = mode2([1,2,3,1,2,3,1,2,3]),
    all_tests_passed.


mode([X|Xs]=L) -> 
    XCount = count(X, L),
    mode(Xs, [ {X, XCount} ]).  %Use the first element as the mode.

mode([], Modes) ->
    extract_results(Modes);
mode([X|Xs]=L, [ {_, Count}| _ ]=Modes) ->
    XCount = count(X, L),
    if 
        XCount > Count      -> mode(Xs, [{X, XCount}]); %Use new mode Modes list.
        XCount =:= Count    -> mode(Xs, [{X, XCount} | Modes]); %A tie, so add new mode to Modes list.
        true                -> mode(Xs, Modes) %Not a mode.
    end.

%---------------------------

mode2([X|Xs]=L) -> 
    XCount = count(X, L),
    mode2(Xs, [ {X, XCount} ]).  %Use the first element as a default mode.

mode2([], Modes) ->
    extract_results(Modes);
mode2([X|Xs]=L, Modes) ->
    XCount = count(X, L),
    NewModes = add_if_mode(X, XCount, Modes),
    mode2(Xs, NewModes).

add_if_mode(X, XCount, [ {_M, MCount}|_Ms ] ) when XCount > MCount ->
    [{X, XCount}];         %Replace old mode with new mode.
add_if_mode(X, XCount, [ {_M, MCount}|_Ms ]=Modes ) when XCount =:= MCount ->
    [{X, XCount} | Modes]; %A tie, add new mode to Modes list.
add_if_mode(_, XCount, [ {_M, MCount}|_Ms ]=Modes ) when XCount < MCount ->
     Modes.                %X is not a mode, so return Modes unchanged.


count(_, []) -> 0;
count(N, L) ->
    count(N, L, 0).

count(_, [], Count) ->
    Count;
count(N, [N|Xs], Count) ->
    count(N, Xs, Count+1);
count(N, [_|Xs], Count) ->
    count(N, Xs, Count).


extract_results([{_, 1}|_]) -> []; %Numbers with counts of 1 are not modes.
extract_results(Modes) -> extract_results(Modes, []).

extract_results([{M, _Count}|Ms], Acc) ->
    extract_results(Ms, [M | Acc]);
extract_results([], Acc) ->
    Acc.