More functions over lists - FP in Erlang 2.27

morefuns.erl

%% More functions over lists
%% FP in Erlang 2.27

-module(morefuns).
-export(
   [ join/2
   , concat/1
   , member/2
   , mergesort/1
   , quicksort/1
   , insertionsort/1
   , perms/1
   , test/0
   ]).

%%---------------------------------------
%%
%% Joining lists together
%%
%% @doc Join two lists together like '++' operator:
%% eg. "hel"++"lo" = "hello"
%%

%% @doc Reverse list

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

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

test_reverse() ->
    [3, 2, 1] = reverse([1, 2, 3]),
    ok.

join(L, R) ->
    reverse(reverse(L), R).

test_join() ->
    "hello" = join("hel", "lo"),
    ok.

%%
%% @doc Concatenate list of lists
%%

concat(Result, []) -> Result;
concat(L, [X| Xs]) ->
    concat(join(L, X), Xs).

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

test_concat() ->
    "goodbye" = concat(["goo", "d", "", "by", "e"]),
    ok.

%%--------------------------------------
%% Testing membership
%%
%% @doc Test whether first argument is a member of the second argument (list)
%%

member(_X, []) -> false;
member(X, [X | _Ys]) -> true;
member(X, [_Y | Ys]) -> member(X, Ys).

test_member() ->
    true = member(2,[2,0,0,1]),
    false = member(20,[2,0,0,1]),
    ok.

%%--------------------------------------
%% MERGE SORT
%%

%% @doc Merge two sorted lists into one

merge([], [], Merged) ->
    reverse(Merged);
merge([L| Ls], [], Merged) ->
    merge(Ls, [], [L| Merged]);
merge([], [R| Rs], Merged) ->
    merge([], Rs, [R| Merged]);
merge([L| Ls], [R| Rs], Merged) when L < R ->
    merge(Ls, [R | Rs], [L| Merged]);
merge([L| Ls], [R| Rs], Merged) ->
    merge([L| Ls], Rs, [R| Merged]).

merge(L, R) ->
    merge(L, R, []).

test_merge() ->
    [1, 2, 3, 4] = merge([1, 3], [2, 4]),
    [1, 2, 2, 2, 4, 7, 8] = merge([1, 2, 2, 7, 8], [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 Split the list into two halves

split(0, Ls, Rs) -> {reverse(Ls), Rs};
split(N, Ls, [R| Rs] ) when N > 0 ->
    split(N - 1, [R| Ls], Rs).

split(List) ->
    Len = len(List),
    N = Len div 2,
    split(N, [], List).

test_split() ->
    {[1], [2]} = split([1, 2]),
    {[], [1]} = split([1]),
    ok.

%% @doc Is a list sorted?

is_sorted([]) -> true;
is_sorted([_X]) -> true;
is_sorted([X, Y| Xs]) when X =< Y ->
    is_sorted(Xs);
is_sorted(_) -> false.

test_sorted() ->
    true = is_sorted([1,2,2,3]),
    ok.

%% @doc Merge sort: divide the list into two halves of (approximately) equal
%% length, sort them (recursively) and then merge the results.

mergesort(List) ->
    case is_sorted(List) of
        true -> List;
        false ->
            {L, R} = split(List),
            merge(mergesort(L), mergesort(R))
    end.

test_mergesort() ->
    [1, 2, 3] = mergesort([3, 2, 1]),
    [1, 2, 2, 2, 3, 4, 5, 6] = mergesort([3, 2, 1, 2, 6, 5, 4, 2]),
    ok.

%%--------------------------------------
%% QUICKSORT
%%

%% @doc Divide given list into two lists
%%
%% First argument is a list (to be divided) and second is so called pivot.
%%
%% Split the list into lists: Less and NotLess. Less contains elements that are
%% less than pivot and NotLess contains elements equal or greater than pivot.

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] ).

divide(List, Pivot) ->
    divide(List, Pivot, [], []).

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

%% @doc Quicksort: split the list into two, sort the two halves and join the
%% results together.

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

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

%%--------------------------------------
%% INSERTION SORT
%%

%% @doc Return list with inserted element in the correct place

insert(Xs, [], Z) ->
    join(reverse(Xs), [Z]);
insert(Xs, [Y| Ys], Z) when Z =< Y ->
    join(reverse(Xs), [Z, Y| Ys]);
insert(Xs, [Y| Ys], Z) ->
    insert([Y| Xs], Ys, Z).

insert(List, Z) ->
    insert([], List, Z).

test_insert() ->
    [1, 2, 3, 4] = insert([1, 2, 4], 3),
    [1, 2, 2, 3, 4] = insert([1, 2, 3, 4], 2),
    [1, 2, 3, 4] = insert([1, 2, 3], 4),
    ok.

%% @doc Sort the tail of the list and then insert the head of the list in the
%% correct place.

insertionsort(Ls, []) -> Ls;
insertionsort(Ls, [R| Rs]) ->
    insertionsort(insert(Ls, R), Rs).

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

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

%% PERMUTATIONS

%% @doc Generate new lists with a header attached

hd_to_lists(_H, [], Out) -> Out;
hd_to_lists(H, [List| Lists], Out) ->
    case not member(H, List) of
        true -> hd_to_lists(H, Lists, [[H| List]| Out]);
        false -> hd_to_lists(H, Lists, Out)
    end.

test_hd_to_lists() ->
    [[1,6,7],[1,4,5],[1,2,3]] = hd_to_lists(1, [[2,3],[4,5],[6,7]], []),
    ok.

%% @doc Input: List, Lists
%% For every element of List generate new lists and join them

list_to_lists([], _Lists, Out) -> reverse(Out);
list_to_lists([H|T], [], Out) ->
   list_to_lists(T, [], [[H]|Out]);
list_to_lists([H|T], Lists, Out) ->
    L = hd_to_lists(H, Lists, []),
    list_to_lists(T, Lists, join(L, Out)).

test_list_to_lists() ->
    L= [1, 2],
    Ls = [[3, 4],[5, 6]],
    [[1,3,4],[1,5,6],[2,3,4],[2,5,6]] = list_to_lists(L, Ls, []),
    ok.

%% @doc Iterate N times list_to_lists

next_lists(0, _List, Lists) -> Lists;
next_lists(N, List, Lists) ->
    NewLists = list_to_lists(List, Lists, []),
    next_lists(N - 1, List, NewLists).

%% @doc Return new list with no duplicates

remove_duplicates([], Out) -> reverse(Out);
remove_duplicates([X| Xs], Out) ->
    case member(X, Out) of
        true -> remove_duplicates(Xs, Out);
        false -> remove_duplicates(Xs, [X| Out])
    end.

%% @doc For given list return list of its permutations (lists)

perms([]) -> [[]];
perms(List) ->
    L = remove_duplicates(List, []),
    next_lists(len(L), L, []).

test_perms() ->
    [[]] = perms([]),
    [[1,2,3,4], [1,2,4,3], [1,3,2,4], [1,3,4,2],
     [1,4,2,3], [1,4,3,2], [2,1,3,4], [2,1,4,3],
     [2,3,1,4], [2,3,4,1], [2,4,1,3], [2,4,3,1],
     [3,1,2,4], [3,1,4,2], [3,2,1,4], [3,2,4,1],
     [3,4,1,2], [3,4,2,1], [4,1,2,3], [4,1,3,2],
     [4,2,1,3], [4,2,3,1], [4,3,1,2], [4,3,2,1]]
        = perms([1,2,3,4]),
    ok.

test() ->
    ok = test_reverse(),
    ok = test_join(),
    ok = test_concat(),
    ok = test_member(),
    ok = test_divide(),
    ok = test_quicksort(),
    ok = test_merge(),
    ok = test_len(),
    ok = test_split(),
    ok = test_sorted(),
    ok = test_mergesort(),
    ok = test_insert(),
    ok = test_insertionsort(),
    ok = test_hd_to_lists(),
    ok = test_list_to_lists(),
    ok = test_perms(),
    ok.

WOW!! Amazing code you have here, Marek! Nicely done!

Thanks for your kind words!