Sunday, October 05, 2008

A first refactoring of A-star in Erlang

Clearly in earlier (unpublished) attempts at using the case construct in Erlang, I had been making some very n00bish mistakes. Today with a set of code that worked, and could be modified step-wise, I find that when used properly, it does make things terser -- fewer intermediate variables, and without the true branch meaning "false" -- and then lets me pattern match on expressions that are functions of arguments, rather than only the arguments themselves.

The use of if for crossing_time and display gives a natural if/else if cascade (as the most "traditional" analogue for what the Erlang if does). Most of the time, using case has made the code terser (removing the need for most temporaries in simple binary choices, if nothing else -- here best_step is an exception, where the temporary looks to be a necessity); for update, it was about neutral. Maybe there is a trick I am missing, but anything going through a binary looks like it would make crossing_time and display more cumbersome, rather than less.


Unknown said...

Wow, that code cleaned up nicely!

The remaining "if" statements in crossing_time and display are fine. However, just for the mental exercise, you can also think of them in terms of operations over lists. The crossing_time fun, for example, operates over a list of [16, 8, 4, 2] where 2 represents the current "true" branch of the "if", and display operates over the list [16, 8, 4, 2, 1] where 1 represents the "true" branch. Folding over these lists would work, but note that doing so would require walking the whole list. While that's admittedly not very expensive, it still costs more than the short-circuiting "if". You could do this to walk the list while still short-circuiting:

crossing_time(Swap) ->
  crossing_time(Swap, [{16, 10}, {8,5}, {4,2}, {2,1}]).
crossing_time(_, [{2,1}]) -> 1;
crossing_time(Swap, [{Val, Result} | _])
 when Swap band Val =/= 0 ->
crossing_time(Swap, [_ | T]) -> crossing_time(Swap, T).

I wouldn't argue that that's clearer than the "if" though.

Anonymous said...

I can't see the Erlang Code. It shows up for an instant when I click on the title, then it disapears. Thanks!

Steve Gilham said...

It appears that the syntax highlighting for Erlang is working for FireFox, but is doing something weird for IE.

If you go to the whole-month page for October, the Erlang code shows but isn't highlighted; and as noted vanishes altogether if you just go to the single entry.

Steve Gilham said...

There was a spurious comma in the highlighting script, which borked IE. Fixed now.