the power of pairing

In a previous post I talked about an example where a pair performed better than either individually. Here's another small example that happened to me today.

My very good friend Syver was running a coding dojo in Erlang. A test for the filter exercise looked like this:

odd(Integer) when Integer rem 2 == 1 ->
    true;
odd(_) ->
    false.

filter_test() ->
    ?assertEqual([3, 1], 
      filter(fun(Elem) -> odd(Elem) end, [1, 2, 3, 4])).    

I don't know Erlang at all, so Syver helped me out with this first-cut version:

filter(_, []) ->
    [];
filter(Fun, [Head|Tail]) ->
    filter_helper(Fun(Head), Fun, Head, Tail, []).

filter_helper(true, Fun, TrueElement, [Head|Tail], Result) ->
    filter_helper(Fun(Head), Fun, Head, Tail, [TrueElement|Result]);
filter_helper(true, _, TrueElement, [], Result) ->
    [TrueElement|Result];
filter_helper(false, Fun, _, [Head|Tail], Result) ->
    filter_helper(Fun(Head), Fun, Head, Tail, Result);
filter_helper(false, _, _, [], Result) ->
    Result

I realized Erlang is a lot like Prolog which I knew in the dim and distant past. I stared at the code and after several minutes something about it started nagging me. It was the splitting of the list into it's Head and Tail elements in both filter and filter_helper. I wondered if this duplication could be avoided by making filter_helper call back into filter. After several false attempts I came up with:

filter(_, []) ->
    [];
filter(Fun, [Head|Tail]) ->
    filter_helper(Fun(Head), Fun, Head, Tail).

filter_helper(true, Fun, TrueElement, List) ->
    X = filter(Fun,List),
    [TrueElement|X];
filter_helper(false, Fun, _FalseElement, List) ->
    filter(Fun, List).

Then Syver showed me how the use of X could be collapsed:

filter(_, []) ->
    [];
filter(Fun, [Head|Tail]) ->
    filter_helper(Fun(Head), Fun, Head, Tail).

filter_helper(true, Fun, TrueElement, List) ->
    [TrueElement|filter(Fun, List)];
filter_helper(false, Fun, _FalseElement, List) ->
    filter(Fun, List).

We did some argument renaming:

filter(_, []) ->
    [];
filter(Fun, [Head|Tail]) ->
    filter_helper(Fun(Head), Fun, Head, Tail).

filter_helper(true, Fun, Head, List) ->
    [Head|filter(Fun, List)];
filter_helper(false, Fun, _, List) ->
    filter(Fun, List).

Then Syver noticed that we could pass Head,Tail as a single [Head|Tail] argument:

filter(_, []) ->
    [];
filter(Fun, [Head|Tail]) ->
    filter_helper(Fun(Head), Fun, [Head|Tail]).

filter_helper(true, Fun, [Head|Tail]) ->
    [Head|filter(Fun, [Head|Tail])];
filter_helper(false, Fun, [_|Tail]) ->
    filter(Fun, Tail).

We agreed that filter_helper was better as filter:

filter(_, []) ->
    [];
filter(Fun, [Head|Tail]) ->
    filter(Fun(Head), Fun, [Head|Tail]).

filter(true, Fun, [Head|Tail]) ->
    [Head|filter(Fun, [Head|Tail])];
filter(false, Fun, [_|Tail]) ->
    filter(Fun, Tail).

As a final polish Syver refactored to this:

filter(_, []) ->
    [];
filter(Fun, [Head|Tail] = List) ->
    filter(Fun(Head), Fun, List).

filter(true, Fun, [Head|Tail]) ->
    [Head|filter(Fun, [Head|Tail])];
filter(false, Fun, [_|Tail]) ->
    filter(Fun, Tail).

and then, again, after the dojo, thanks to Syver's comment below, to this:

filter(_, []) ->
    [];
filter(Fun, [Head|_] = List) ->
    filter(Fun(Head), Fun, List).

filter(true, Fun, [Head|Tail]) ->
    [Head|filter(Fun, [Head|Tail])];
filter(false, Fun, [_|Tail]) ->
    filter(Fun, Tail).

We agreed that the final version was definitely better than either of us could have come up with individually.