Constructing lists with recursive functions - FP in Erlang 2.18

reclists.erl

%% FP in Erlang 2.18
%% Constructing lists with recursive functions
%%

-module(reclists).
-export(
   [ double/1
   , even/1
%  , divide/4
%  , sort/1
%  , len/1
%  , take2/2
   , median/1
%  , how_many/2
%  , occurences/1
%  , reverse/1
%  , to_list/1
%  , sort_gen/2
   , modes/1
   , test/0
   ]).

%% @doc Return a list with elements multiplied by 2

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

test_double() ->
    [8] = reclists:double([4]),
    [2, 4, 6] = reclists:double([1, 2, 3]),
    [2, 4, 6, 8, 10] = reclists:double([1, 2, 3, 4, 5]),
    ok.

%% @doc Extract even numbers into a new list

even([]) -> [];
even([X | Xs]) ->
    case X rem 2 of
        0 -> [X | even(Xs)];
        1 -> even(Xs)
    end.

test_even() ->
    [] = reclists:even([1, 3, 5]),
    [2, 4, 6] = reclists:even([1, 2, 3, 4, 5, 6]),
    ok.

%% @doc Divide given list into two lists:
%% Less contains elements less than given Y
%% NotLess contains elements equal or greater than Y
%%

divide([], _, Less, NotLess) -> {Less, NotLess};
divide([X | Xs], Y, Less, NotLess) when X < Y ->
    divide(Xs, Y, [X | Less], NotLess);
divide([X | Xs], Y, Less, NotLess) ->
    divide(Xs, Y, Less, [X | NotLess] ).

test_divide() ->
    {[1, 3, 2], [5, 7, 8, 6]} = divide([2, 3, 1, 6, 8, 7, 5], 4, [], []),
    ok.


%% @doc Sort list
%%
%% Here is a description:
%%
%% Take the first element X of unsorted list and divide this list with X removed
%% into two lists using divide/4. For example for unsorted list [4, 2, 3, 1, 6,
%% 8, 7, 5], X = 4 and divide gives us {[1, 3, 2], [5, 7, 8, 6]}. After this
%% step we obtain a "partially" sorted list [1, 3, 2] ++ [4] ++ [5, 7, 8, 6]
%%
%% Next recursively apply sort/1 for [1, 3, 2] and [5, 7, 8, 6] until all lists
%% are sorted. Finally concatenate all lists.
%%

sort([]) -> [];
sort([X | Xs]) ->
    {Less, NotLess} = divide(Xs, X, [], []),
    sort(Less) ++ [X] ++ sort(NotLess).

test_sort() ->
    [1, 2, 3, 4, 5, 6, 7, 8] = sort([4, 2, 3, 1, 6, 8, 7, 5]),
    [1, 2, 2, 2, 2, 3, 4, 5] = sort([1, 2, 3, 2, 2, 5, 2, 4]),
    ok.

%% @doc Return length of a list

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

test_len() ->
    5 = len([1,2,3,4,5]),
    ok.

%% @doc Take element N and N+1 from a list

take2(1, [X, Y | _]) ->
    {X, Y};
take2(N, [_ | Xs]) ->
    take2(N - 1, Xs).

test_take2() ->
    {1, 2} = take2(1, [1,2,3,4,5]),
    {2, 3} = take2(2, [1,2,3,4,5]),
    ok.

%% @doc Calculate median of a list of integers

median(List) ->
    % sort given list
    Sorted = sort(List),
    Len = len(Sorted),
    % take two middle elements of sorted list
    {N, Nplus1} = take2(Len div 2, Sorted),
    % if list is of even length we should return average
    TakeAverage = Len rem 2 == 0,
    case TakeAverage of
        true -> (N + Nplus1) / 2;
        false -> Nplus1
    end.

test_median() ->
    3 = median([1, 3, 5, 4, 2]),
    2.5 = median([1, 2, 3, 4]),
    ok.

%%
%% @doc How many times a value occurs in the list of integers
%%

how_many(_, [], N) -> N;
how_many(X, [X| Xs], N) ->
    how_many(X, Xs, N + 1);
how_many(X, [_| Xs], N) ->
    how_many(X, Xs, N).

how_many(X, List) ->
    how_many(X, List, 0).

test_how_many() ->
    2 = how_many(2, [1,2,2,3,4]),
    1 = how_many(1, [1,4,2,4,4]),
    3 = how_many(4, [1,4,2,4,4]),
    ok.

%% @doc Return a list without a given element

remove(_, [], NoX) -> NoX;
remove(X, [X| Xs], NoX) ->
    remove(X, Xs, NoX);
remove(X, [Y| Xs], NoX) ->
    remove(X, Xs, [Y| NoX]).

remove(X, List) ->
    remove(X, List, []).

test_remove() ->
    [4, 3, 1] = remove(2, [1, 2, 2, 3, 4]),
    ok.

%% @doc Generate list of occurences from a list of integers. Occurence is a
%% tuple {Number, HowManyTimes}

occurences(List, Occurences) ->
    case List of
        [] -> Occurences;
        [X| _] ->
            HowMany = how_many(X, List),
            NewList = remove(X, List),
            occurences(NewList, [{X, HowMany} | Occurences])
    end.

occurences(List) ->
    occurences(List, []).

test_occurences() ->
    [{2, 2}, {3, 1}, {1, 1}] = occurences([1, 2, 2, 3]),
    ok.

%% @doc Generalized divide function
%%
%% Instead of '<' operator we require to pass IsLess(X: int, Y:int) -> bool
%% function as additional parameter

divide_gen(_IsLess, [], _, Less, NotLess) -> {Less, NotLess};
divide_gen(IsLess, [X | Xs], Y, Less, NotLess) ->
    % IsLess cannot be used in a guard
    case IsLess(X, Y) of
        true ->
            divide_gen(IsLess, Xs, Y, [X | Less], NotLess);
        false ->
            divide_gen(IsLess, Xs, Y, Less, [X | NotLess] )
    end.

test_divide2() ->
    IsLess = fun (X, Y) -> X < Y end,
    {[1, 3, 2], [5, 7, 8, 6]} = divide_gen(IsLess, [2, 3, 1, 6, 8, 7, 5], 4, [], []),
    ok.

%% @doc Generalized sort function
%%
%% Instead of '<' operator we require to pass IsLess(X: int, Y:int) -> bool
%% function as additional parameter

sort_gen(_IsLess, []) -> [];
sort_gen(IsLess, [X | Xs]) ->
    {Less, NotLess} = divide_gen(IsLess, Xs, X, [], []),
    sort_gen(IsLess, Less) ++ [X] ++ sort_gen(IsLess, NotLess).

test_sort2() ->
    IsLess1 = fun (X, Y) -> X < Y end,
    [1, 2, 3, 4, 5, 6, 7, 8] = sort_gen(IsLess1, [4, 2, 3, 1, 6, 8, 7, 5]),
    [1, 2, 2, 2, 2, 3, 4, 5] = sort_gen(IsLess1, [1, 2, 3, 2, 2, 5, 2, 4]),
    IsLess2 =
        fun ({X, HowManyX}, {Y, HowManyY}) ->
                case HowManyX == HowManyY of
                    true -> X < Y;
                    false -> HowManyX < HowManyY
                end
        end,
    [{1,1},{2,1},{5,1},{6,1},{3,2},{4,2}] =
        sort_gen(IsLess2, [{4,2},{3,2},{5,1},{2,1},{6,1},{1,1}]),
    ok.

%% @doc reverse the list

reverse(InList, Reversed) ->
    case InList of
        [] -> Reversed;
        [X | Xs] -> reverse(Xs, [X | Reversed])
    end.

reverse(List) ->
    reverse(List, []).

%% @doc Convert list of occurences to list of integers

to_list(Occurences, Integers) ->
    case Occurences of
        %% reverse/1 because we want to preserve the order
        [] -> reverse(Integers);
        [{X, _HowMany}| Xs] -> to_list(Xs, [X | Integers])
    end.

to_list(Occurences) ->
    to_list(Occurences, []).

test_to_list() ->
    [4, 3, 5, 2, 6, 1] = to_list([{4,2},{3,2},{5,1},{2,1},{6,1},{1,1}]),
    ok.

%% @doc Return the list of numbers that occur most frequently in the list in
%% descendig order. For the same frequency greater integer goes first.

modes(List) ->
    Occurences = occurences(List),
    IsLess =
        fun ({X, HowManyX}, {Y, HowManyY}) ->
                case HowManyX == HowManyY of
                    true -> X < Y;
                    false -> HowManyX < HowManyY
                end
        end,
    Sorted = sort_gen(IsLess, Occurences),
    reverse(to_list(Sorted)).

test_modes() ->
    [3, 2, 1] = modes([1, 2, 2, 3, 3, 3]),
    [1, 3, 2] = modes([1, 2, 2, 3, 3, 1, 1, 3, 1]),
    [3, 2, 1] = modes([1, 2, 3]),
    ok.

test() ->
    ok = test_double(),
    ok = test_even(),
    ok = test_divide(),
    ok = test_sort(),
    ok = test_len(),
    ok = test_take2(),
    ok = test_median(),
    ok = test_how_many(),
    ok = test_remove(),
    ok = test_occurences(),
    ok = test_divide2(),
    ok = test_sort2(),
    ok = test_to_list(),
    ok = test_modes(),
    ok.

This is really great code! Huge kudos to you!
Maybe the only thing I would've done differently is to use pattern-matching a bit more aggressively…

        fun ({X, HowManyX}, {Y, HowManyX}) -> X < Y
          ; ({X, HowManyX}, {Y, HowManyY}) -> HowManyX < HowManyY
        end,

occurences([], Occurences) -> Occurences;
occurences([X| _] = List, Occurences) ->
    HowMany = how_many(X, List),
    NewList = remove(X, List),
    occurences(NewList, [{X, HowMany} | Occurences]).

Very nice function definition! Thank you!