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.

4 comments :

Anonymous said...

Toggle button isn't working

Steve Gilham said...

Fixed. Forgot to rename the toggle function.

lf.hl said...

Cool, can u compare it in more detail? Erlang vs. F#?

Steve Gilham said...

The two functionally complete, though still somewhat polishable, versions, F# and Erlang are mainly token-for-token copies. The real differences are consequences of the differing type systems. I have to make some explicit type specifications for the F# version -- type Graph <'a,'b&gt, use of Option('a) whereas on the Erlang side I don't need the former and can use pattern matching for the latter. I can also use pattern matching at the function argument level rather than using match clauses inside.

There are more differences in the half-way stages -- the F# type system needs a lot more scaffolding with explicit type declarations in the construction stages, which can be taken down when the whole system is complete (rather like building an arch).