functions over lists

join.erl

-module(join).

-import(lists,[foldr/3,foldl/3,filter/2,split/2,flatmap/2,map/2,seq/2]).

-export([join/2,concat/1,member/2,qsort/1,msort/1,isort/1,perms/1]).

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

reverse(Xs) ->
    foldl(fun (E,A) -> [E|A] end, [], Xs).

join(Xs, Ys) ->
    join_(reverse(Xs), Ys).

concat(Xs) ->
    foldr(fun join/2, [], Xs).

member(_, []) ->
    false;
member(X, [X|_]) ->
    true;
member(X, [_|Ys]) ->
    member(X,Ys).

qsort([]) ->
    [];
qsort([X|Xs]) ->
    L = filter(fun(E) -> E =< X end, Xs),
    R = filter(fun(E) -> E > X end, Xs),
    qsort(L) ++ [ X | qsort(R)].

merge([X|Xs]=A, [Y|Ys]=B) ->
    if X < Y ->
	    [ X | merge(Xs, B)];
       true ->
	    [ Y | merge(A, Ys)]
    end;
merge(A, []) ->
    A;
merge([], B) ->
    B.

msort([]=E) ->
    E;
msort([_]=E) ->
    E;
msort(L) ->
    {Xs,Ys} = split(length(L) div 2, L),
    merge(msort(Xs), msort(Ys)).

insert(Y, []) ->
    [Y];
insert(Y, [X|Xs]=E) ->
    if Y =< X ->
	    [Y | E];
       true -> [X | insert(Y, Xs)]
    end.

isort([]=E) ->
    E;
isort([X|Xs]) ->
    insert(X, isort(Xs)).

take_nth(N,Xs) ->
    {L,[R|Rs]} = split(N,Xs),
    {R,L ++ Rs}.

perms([]) ->
    [[]];
perms(Xs) ->
    S = map(fun(N) -> take_nth(N,Xs) end, seq(0, length(Xs)-1)),
    flatmap(fun({E,L}) -> map(fun(P) -> [E | P] end, perms(L)) end, S).

join_tests.erl

-module(join_tests).
-import(join,[join/2,concat/1,member/2,qsort/1,msort/1,isort/1,perms/1]).

-include_lib("eqc/include/eqc.hrl").
-include_lib("eunit/include/eunit.hrl").

-compile(export_all).

prop_join() ->
    ?FORALL(A, list(int()), ?FORALL(B, list(int()), join(A,B) == A++B)).

prop_concat() ->
    ?FORALL(A, list(list(int())), concat(A) == lists:concat(A)).

small_int() ->
    ?SUCHTHAT(N, int(), N < 100).

prop_member() ->
    ?FORALL(A, small_int(), ?FORALL(B, list(small_int()), member(A,B) == lists:member(A,B))).

prop_qsort() ->
    ?FORALL(A, list(int()), qsort(A) == lists:sort(A)).

prop_isort() ->
    ?FORALL(A, list(int()), isort(A) == lists:sort(A)).

prop_msort() ->
    ?FORALL(A, list(int()), msort(A) == lists:sort(A)).

fact(0) ->
    1;
fact(N) ->
    N * fact(N-1).

small_list() ->
    ?SUCHTHAT(N, list(int()), length(N) < 10).

prop_perms() ->
    ?FORALL(A, small_list(), length(perms(A)) == fact(length(A))).