numbers.erl

-module( numbers ).
-include_lib("eunit/include/eunit.hrl").
-export( [ double/1, evens/1, modes/1, median/1 ] ).

% I think the point of double is to make us write map
map( _F, [] ) ->
    [];
map( F, [ X | Xs ] ) ->
    [ F( X ) | map( F, Xs ) ].

% I think the point of evens is to make us write filter
filter( _F, [] ) ->
    [];
filter( F, [ X | Xs ] ) ->
    case F( X ) of
        true -> [ X | filter( F, Xs ) ];
        _ -> filter( F, Xs )
    end.

% bifilter returns two lists, one with elements for which F returns true,
% the other for elements for which F returns false
bifilter( F, Xs ) ->
    bifilter( F, Xs, [], [] ).

bifilter( _F, [], Matches, NoMatches ) ->
    { Matches, NoMatches };
bifilter( F, [ X | Xs ], Matches, NoMatches ) ->
    case F( X ) of
        true  -> bifilter( F, Xs, [ X | Matches ], NoMatches );
        false -> bifilter( F, Xs, Matches, [ X | NoMatches ] )
    end.

% double

double( Xs ) ->
    map( fun( X ) -> 2 * X end, Xs ).

% double tests

double_empty_test() ->
	[] = double( [] ).
double_simple_test() ->
	[ 4 ] = double( [ 2 ] ).
double_full_test() ->
	[ 4, 10.8, 2, 13.4, 9.2 ] = double( [ 2, 5.4, 1, 6.7, 4.6 ] ).

% evens

evens( Xs ) ->
    filter( fun( X ) -> X rem 2 == 0 end, Xs ).

% evens tests

evens_empty_test() ->
	[] = evens( [] ).
evens_none_test() ->
	[] = evens( [ 3, 7, 35, 41, 7 ] ).
evens_all_test() ->
	[ 12, 6, 8, 14 ] = evens( [ 12, 6, 8, 14 ] ).
evens_some_test() ->
	[ 16, 22, 68, 116, 198, 212, 220 ] =
		evens( [ 16, 17, 22, 41, 68, 116, 123, 123, 185, 191, 198, 212, 220, 225 ] ).

% count the number of occurrences of each element of the list
% for use in modes
% returns a lise of tuples { N, O } where O is the number of occurrences of N

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

occurrences( [], R ) ->
    R;
occurrences( [ X | Xs ], R ) ->
	% extract the current occurence tuple for X, and the rest
    { CurrentOccurrence, Rest } = bifilter( fun( { Y, _ } ) -> Y == X end, R ),
    NewOccurrence = case CurrentOccurrence of
    	% no match, first occurence
        [] -> { X, 1 };
        % match, incrememtn counter
        [ { X, N } ] -> { X, N + 1 }
    end,
    occurrences( Xs, [ NewOccurrence | Rest ] ).

% filter a list of occurrence tuples to keep only the maximum ones

max_occurrences( [] ) ->
    [];
max_occurrences( [ { N, OccN } | RestOcc ] ) ->
    max_occurrences( RestOcc, OccN, [ N ] ).

max_occurrences( [], _Max, MaximalNs ) ->
    MaximalNs;
max_occurrences( [ { N, OccN } | RestOcc ], Max, MaximalNs ) ->
    if
    	% N occurs less than current max, discard
        OccN <  Max -> max_occurrences( RestOcc, Max, MaximalNs );
    	% N occurs as much as current max, add N to MaximalNs
        OccN == Max -> max_occurrences( RestOcc, Max, [ N | MaximalNs ] );
    	% N occurs more than current max, OccN is new max, N is new result
        OccN >  Max -> max_occurrences( RestOcc, OccN, [ N ] )
    end.

% modes: elements of a list that occur the most often

modes( Xs ) ->
    max_occurrences( occurrences( Xs ) ).

% modes tests

modes_empty_test() ->
	[] = modes( [] ).
modes_single_test() ->
	[ 6 ] = modes( [ 6, 3, 8, 3, 6, 6, 8, 2, 3, 6 ] ).
modes_multiple_test() ->
	[ 6, 8, 5 ] = modes( [ 6, 3, 8, 3, 5, 6, 6, 8, 2, 5, 8, 3, 6, 8, 5, 5 ] ).

% order two numbers, fir use by sort
order( A, B ) when A > B ->
    { B, A };
order( A, B ) ->
    { A, B }.

% bubble sort
sort( L = [] ) ->
    L;
sort( L = [ _ ] ) ->
    L;
sort( [ X1, X2 | Xs ] ) ->
    % order the first two elements
    { A, B } = order( X1, X2 ),
    % sort starting from second element
    Sorted = [ S1, S2 | _Rest ] = [ A | sort( [ B | Xs ] ) ],
    % if first element is not larger than new second, we’re done
    case S1 > S2 of
        true -> sort( Sorted );
        false -> Sorted
    end.

% numbers:sort( [ 3, 2, 1, 5, 4, 8, 12, 4, 1 ] ).
% numbers:sort( [ 2, 2, 1 ] ).

sort_empty_test() ->
    [] = sort( [] ).
sort_one_test() ->
    [ 42 ] = sort( [ 42 ] ).
sort_simple_test() ->
    [ 1, 2, 5 ] = sort( [ 2, 1, 5 ] ).
sort_duplicates_test() ->
    [ 3, 3, 6, 8 ] = sort( [ 6, 3, 8, 3 ] ).
sort_duplicate_bug_test() ->
    [ 1, 1, 2, 3, 4, 4, 5, 8, 12 ] = sort( [ 3, 2, 1, 5, 4, 8, 12, 4, 1 ] ).
sort_duplicate_bug_base_test() ->
    [ 1, 2, 2 ] = sort( [ 2, 2, 1 ] ).
sort_to_be_sure_test() ->
    [ 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3 ]
    = sort( [ 2, 2, 2, 2, 3, 3, 1, 1, 1, 1, 1, 1, 2 ] ).
sort_large_test() ->
    [ 16, 17, 22, 41, 68, 116, 123, 123, 185, 191, 198, 212, 220, 225, 229, 241,
      298, 319, 330, 334, 335, 344, 352, 355, 371, 401, 485, 502, 609, 634, 646,
      658, 673, 678, 679, 758, 758, 774, 798, 805, 820, 830, 837, 862, 883, 891,
      910, 968, 969, 993 ]
     = sort( [ 820, 22, 41, 609, 968, 634, 862, 335, 352, 830, 837, 758, 658,
       68, 116, 229, 401, 485, 16, 191, 910, 678, 371, 891, 969, 198, 334, 123,
       798, 673, 17, 225, 883, 805, 502, 220, 344, 758, 330, 355, 319, 679, 646,
       185, 774, 298, 212, 241, 123, 993 ] ).

median( Xs ) ->
	Ss = sort( Xs ),
	medians( Ss, 0, Ss, 0 ).

% eat through the list two elements at a time and one element at a time, count elements
% once the fast list is empty, the slow list gives us the middle element
medians( _Fast = [], Middle, _Slow = _, N ) when N rem 2 == 1 ->
	float( Middle );
medians( _Fast = [], Middle, _Slow = [ R | _Rs ], N ) when N rem 2 == 0 ->
	float( ( Middle + R ) / 2 );
medians( _Fast = [ _ ], _Middle, _Slow = [ R | Rs ], N ) ->
	medians( [], R, Rs, N + 1 );
medians( _Fast = [ _, _ | Xs ], _Middle, _Slow = [ R | Rs ], N ) ->
	medians( Xs, R, Rs, N + 2 ).

median_one_test() ->
	3.0 = median( [ 3 ] ).
median_two_test() ->
	4.0 = median( [ 2, 6 ] ).
median_three_test() ->
	6.0 = median( [ 3, 16, 6 ] ).
median_four_test() ->
	21.0 = median( [ 7, 45, 25, 17 ] ).