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.

5 comments:

  1. Anonymous11:59 pm

    I wonder whether this is a rule or an exception. Looking back over the dojos you have run in the past, what were the most inventive solutions you've seen? And were they created by pairs or individuals?

    ReplyDelete
  2. In the cyber-dojo's I run each laptops always has two people. But I mix up the pairs during the dojo - for various reasons, not least of which is to try to generate a feeling of less-ego. So I don't have solutions from individuals to compare to!

    ReplyDelete
  3. Cool Jon. I have a little detail that burns in my eyes though. Replace the Tail variable in the second clause of filter/2 with with _ as Tail is unused there. ;-)

    ReplyDelete
  4. Aha. Yes. Updated :-)

    ReplyDelete
  5. Was fun to have you visit our little study group. Thanks for the tips. Enjoyed trying out cyber-dojo.

    ReplyDelete