Sunday, October 12, 2008

Thrice is a charm — A-star in F#

The real goal of the last couple of exercises, creeping crabwise up on doing something in F# that's not totally trivial.

Having started with the wikipedia pseudo-code, Python was an obvious first real language; then to make it pure functional, Erlang was the obvious choice, before going to F#. And boy was that last step painful at times.

Really Erlang:Python :: F#:C# -- the first two being dynamically typed and forgiving; the other requiring dodges like nullable/option types for the "it didn't work" return cases. Those required some wrestling with the type system in the middle of the conversion from Erlang, though in the end, all the explicit argument type specifications did eventually go away.

The ability to nest functions is where the big changes is structure from the Erlang version show up. I could do a bit more of this -- pulling astar_step into astar, for example, or pulling compatible and equivalent_point into neighbour_nodes -- but I wouldn't want to pull too many long functions inside other ones, simply for clarity.

Also the generic engine could in all three cases be given function arguments to replace the coupling by name in these examples.

It's also annoying that calls always have to go up the source file -- smells a bit of 'C' in comparison with the customary freedom to refer back and forth as in the other implementations (or even in C# or Java) -- so that the algorithm bit is now in the middle and not at the top.

Yes, this does compile with a couple of warnings about incomplete matches in failure cases.

Post a Comment