Erlang Week 2 Consolidation

conso.erl

-module(conso).
-include_lib("eunit/include/eunit.hrl").
-export( [ join/2, concat/1, member/2, each_head/1, each_head/3, perm/1 ] ).

join_test() ->
    [] = join( [], [] ),
    [ 1 ] = join( [ 1 ], [] ),
    [ 2 ] = join( [], [ 2 ] ),
    [ 1, 2, 3, 4, 5 ] = join( [ 1, 2 ], [ 3, 4, 5 ] ).

% join is easy with reverse/2
join( Xs, Ys ) ->
    reverse( reverse( Xs ), Ys ).

concat_test() ->
    "goodbye" = concat( [ "goo", "d", "", "by", "e" ] ),
    "goodbye" = concatj( [ "goo", "d", "", "by", "e" ] ),
    "goodbye" = concatjt( [ "goo", "d", "", "by", "e" ] ).

% I don’t use join in concat, because of the way I made it tail recursive
concat( Ls ) ->
    concat( Ls, [] ).
concat( [], Acc ) ->
    reverse( Acc );
concat( [ L | Ls ], Acc ) ->
    concat( Ls, reverse( L, Acc ) ).

% non tail recursive concat using join
concatj( [] ) ->
    [];
concatj( [ L1 | Ls ] ) ->
    join( L1, concat( Ls ) ).

% tail recursive concat using join
% I don’t like how it keeps going through the accumulator
concatjt( Ls ) ->
    concatjt( Ls, [] ).
concatjt( [], Acc ) ->
    Acc;
concatjt( [ L1 | Ls ], Acc ) ->
    concatjt( Ls, join( Acc, L1 ) ).

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

    [] = reverse( [], [] ),
    [ 1, 2 ] = reverse( [], [ 1, 2 ] ),
    [ 1, 2, 3, 4 ] = reverse( [ 2, 1 ], [ 3, 4 ] ),
    [ 1, 2, 3, 4 ] = reverse( [ 4, 3, 2, 1 ], [] ).

% tail recursive reverse
% Simon calls reverse/2 shunt, but the lists module calls it reverse
reverse( Xs ) ->
    reverse( Xs, [] ).
reverse( [], Ys ) ->
    Ys;
reverse( [ X | Xs ], Ys ) ->
    reverse( Xs, [ X | Ys ] ).

member_test() ->
    true = member( 2, [ 1, 2, 3, 4 ] ),
    true = member( $x, "excellent" ),
    false = member( $y, "excellent" ),
    true = member( great, [ this, is, great ] ).

% test the head, of (short circuit only evaluated if first part fails) test the tail
member( _, [] ) ->
    false;
member( Y, [ X | Xs ] ) ->
    Y == X orelse member( Y, Xs ).

perm_test() ->
    [] = perm( [] ),
    [ [ 2 ] ] = perm( [ 2 ] ),
    [ [ 1, 2 ], [ 2, 1 ] ] = perm( [ 1, 2 ] ),
    [ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ] ] = perm( [ 1, 2, 3 ] ),
    [ [ 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 ]
    ] = perm( [ 1, 2, 3, 4 ] ).

each_head_test() ->
    [] = each_head( [] ),
    [ { 1, [] } ] = each_head( [ 1 ] ),
    [ { 1, [ 2 ] }, { 2, [ 1 ] } ] = each_head( [ 1, 2 ] ),
    [ { 1, [ 2, 3 ] }, { 2, [ 1, 3 ] }, { 3, [ 1, 2 ] } ] = each_head( [ 1, 2, 3 ] ),
    [ { 1, [ 2, 3, 4 ] }, { 2, [ 1, 3, 4 ] }, { 3, [ 1, 2, 4 ] }, { 4, [ 1, 2, 3 ] } ] = each_head( [ 1, 2, 3, 4 ] ).

% helper function for perm. returns a list of tuples, each with the Nth element and the rest of the list
each_head( Xs ) ->
    each_head( Xs, [], [] ).
each_head( [], _Before, Acc ) ->
    reverse( Acc );
each_head( [ X | Xs ], Before, Acc ) ->
    each_head( Xs, [ X | Before ], [ { X, reverse( Before, Xs ) } | Acc ] ).

% for each element of the list, prepend it to each permutation of the rest of the list
perm( [] ) ->
    [];
perm( [ A ] ) ->
    [ [ A ] ];
perm( L ) ->
    Heads = each_head( L ),
    P = fun( { Head, Rest } ) ->
        lists:map( fun( Perm ) -> [ Head | Perm ] end, perm( Rest ) )
    end,
    concat( lists:map( P, Heads ) ).

sort.erl

-module( sort ).
-include_lib("eunit/include/eunit.hrl").
-export( [ split/2, split/3, merge/1, merge_lists/2 ] ).

merge_test() ->
    [] = merge( [] ),
    [ 1 ] = merge( [ 1 ] ),
    [ 1, 2, 3, 4, 5 ] = merge( [ 3, 2, 5, 1, 4 ] ),
    [ 1, 2, 3, 4, 5, 6 ] = merge( [ 3, 6, 2, 5, 1, 4 ] ).

% merge sort: split the list in two, sort each part,
% and merge them by always taking the smaller item
merge( [] ) ->
    [];
merge( L = [ _X ] ) ->
    L;
merge( L = [ _X | _Xs ] ) ->
    { Beg, End } = split( L, length( L ) div 2 ),
    merge_lists( merge( Beg ), merge( End ) ).

merge_lists_test() ->
    [] = merge_lists( [], [] ),
    [ 1 ] = merge_lists( [ 1 ], [] ),
    [ 2 ] = merge_lists( [], [ 2 ] ),
    [ 1, 2 ] = merge_lists( [ 1 ], [ 2 ] ),
    [ 1, 2 ] = merge_lists( [ 2 ], [ 1 ] ),
    [ 1, 2, 3, 4, 5 ] = merge_lists( [ 2, 5 ], [ 1, 3, 4 ] ).

% merge two sorted lists by always taking the smaller item
merge_lists( Xs, [] ) ->
    Xs;
merge_lists( [], Ys ) ->
    Ys;
merge_lists( [ X | Xs ], [ Y | Ys ] ) when X > Y ->
    [ Y | merge_lists( [ X | Xs ], Ys ) ];
merge_lists( [ X | Xs ], [ Y | Ys ] ) ->
    [ X | merge_lists( Xs, [ Y | Ys ] ) ].

split3_test() ->
    { [], [] } = split( [], 0, [] ),
    { [], [] } = split( [], 3, [] ),
    { [], [ 1, 2, 3 ] } = split( [ 1, 2, 3 ], 0, [] ),
    { [ 1 ], [ 2, 3 ] } = split( [ 1, 2, 3 ], 1, [] ),
    { [ 1, 2 ], [ 3 ] } = split( [ 1, 2, 3 ], 2, [] ),
    { [ 1, 2, 3 ], [] } = split( [ 1, 2, 3 ], 3, [] ).

split_test() ->
    { [], [] } = split( [], 0 ),
    { [], [] } = split( [], 3 ),
    { [], [ 1, 2, 3 ] } = split( [ 1, 2, 3 ], 0 ),
    { [ 1 ], [ 2, 3 ] } = split( [ 1, 2, 3 ], 1 ),
    { [ 1, 2 ], [ 3 ] } = split( [ 1, 2, 3 ], 2 ),
    { [ 1, 2, 3 ], [] } = split( [ 1, 2, 3 ], 3 ).

% split a list in two after its element of index N
split( Xs, N ) ->
    split( Xs, N, [] ).
split( [], _N, Acc ) ->
    { lists:reverse( Acc ), [] };
split( Xs, 0, Acc ) ->
    { lists:reverse( Acc ), Xs };
split( [ X | Xs ], N, Acc ) ->
    split( Xs, N - 1, [ X | Acc ] ).

quick_test() ->
    [] = quick( [] ),
    [ 1 ] = quick( [ 1 ] ),
    [ 1, 2, 3, 4, 5 ] = quick( [ 3, 2, 5, 1, 4 ] ),
    [ 1, 2, 3, 4, 5, 6 ] = quick( [ 3, 6, 2, 5, 1, 4 ] ).

% quick sort: split lists into elements smaller or equal, and larger than the pivot
% sort both lists, join them on each side of the pivot
quick( [] ) ->
    [];
quick( [ P | Xs ] ) ->
    { L, R } = bifilter( fun( X ) -> X =< P end, Xs ),
    { LS, RS } = { quick( L ), quick( R ) },
    LS ++ [ P | RS ].

% 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.

insertion_test() ->
    [] = insertion( [] ),
    [ 1 ] = insertion( [ 1 ] ),
    [ 1, 2, 3, 4, 5 ] = insertion( [ 3, 2, 5, 1, 4 ] ),
    [ 1, 2, 3, 4, 5, 6 ] = insertion( [ 3, 6, 2, 5, 1, 4 ] ).

% insertion sort: sort the tail, insert the head at the right position
insertion( [] ) ->
    [];
insertion( [ X | Xs ] ) ->
    insert( X, insertion( Xs ) ).

% insert X at the right position in a sorted list
insert( X, [] ) ->
    [ X ];
insert( X, L = [ Y | _Ys ] ) when X =< Y ->
    [ X | L ];
insert( X, [ Y | Ys ] ) ->
    [ Y | insert( X, Ys ) ].