Functional Mars Rover kata: Railways on Mars

In the previous article, we discussed and implemented domain types for the Mars Rover kata. Now, we will go through the rest of the requirements and implement the command execution functionality.

First, we need to parse an input sequence of characters in order to determine which movement functions should be executed:

	let parseInput chars =
	let commands: Command list = List.Empty
	Seq.toList chars
	|> List.fold (fun commands char ->
	match char with
	| 'L' -> Command.RotateLeft :: commands
	| 'R' -> Command.RotateRight :: commands
	| 'M' -> Command.Move :: commands
	| _ -> commands
	) commands
	|> List.rev

view raw Parsing of an input hosted with ❤ by GitHub

The output of the parseInput function is a list of commands (Command discriminated union type), so we need to map that output to appropriate functions before the execution of a rover movement:

	let toFunc =
	function
	| Command.RotateLeft -> rotateLeft
	| Command.RotateRight -> rotateRight
	| Command.Move -> calculateNewCoordinates

view raw Mapping to the movement functions hosted with ❤ by GitHub

Signature of the toFunc function is:

Command -> (RoverPosition -> RoverPosition)

view raw toFunc signature hosted with ❤ by GitHub

We could easily execute the resulting list of functions just by applying List.fold because every function in the list has the following signature:

RoverPosition -> RoverPosition

view raw Command function signature hosted with ❤ by GitHub

The output of the first function matches the input of the second function. The output of the second function matches the input of the third function, etc. These functions are easily composable.

But, things are not so simple. If we look at the requirements again, we can see that a rover can hit an obstacle. In that case, the rover should stop and return the position of the obstacle. A movement can be either successful or not:

	let move command obstacles position =
	let newPosition = position |> command
	let isObstacle = List.contains newPosition.location obstacles
	newPosition |> if isObstacle then Error else Ok

view raw Single movement function hosted with ❤ by GitHub

Signature of the move function is:

(RoverPosition -> RoverPosition) -> Location list -> RoverPosition -> Result<RoverPosition,RoverPosition>

view raw Movement function signature hosted with ❤ by GitHub

Now, imagine that we have a sequence of movement functions that we want to compose together. The output of the first movement function does not match the input of the second movement function. The output of the second movement function does not match the input of the third movement function, etc. The first two parameters (command and the list of obstacles) can be baked into the move function but, the issue then is the signature of the partially applied function:

RoverPosition -> Result<RoverPosition,RoverPosition>

view raw RoverPosition to Result of RoverPosition hosted with ❤ by GitHub

Luckily, the solution to this problem already exists in functional programming: Railway Oriented Programming. I strongly suggest you read the original explanation by Scott Wlaschin.

I will introduce you to the basics and then we will try to apply the theory to our problem.

So, why railways? Well, railways have tracks. A track can be a good metaphor for a function. Functions are transformations that turn input into an output (Figure 1). The composition then comes naturally as long as the output of one function matches the input of some other function.

Figure 1.

When we try to execute a movement function, we either hit an obstacle or we proceed to the next position and execute the next function (if there is one). Railways have another great analogy for this scenario: switches (Figure 2):

Figure 2.

Now it's obvious why we can not glue movement functions together. The move function may end up in one of the two possible tracks. The correct way of applying the composition, in this case, looks like this:

Figure 3.

The top track is the happy path and the bottom track is the failure track. In order to achieve this in the code, we need a function that converts a switch function into a proper two-track function. 

Here's the implementation of that function:

	let bind switchFunction twoTrackInput =
	match twoTrackInput with
	| Ok s -> switchFunction s
	| Error f -> Error f

view raw Bind function hosted with ❤ by GitHub

It takes a switch function (move in our case) as a parameter and returns a new function that takes a two-track input. If the input is Ok it calls the switch function with the appropriate value and if the input is an Error, the switch function is omitted.

With everything in place, we can implement the main command execution function:

	let execute position obstacles commands =
	parseInput commands
	|> List.map toFunc
	|> List.fold (fun position command ->
	bind (move command obstacles) position)
	(Ok position)
	|> formatOutput

view raw Execute with bind function hosted with ❤ by GitHub

And here's the implementation with the F# bind operator:

	let execute position obstacles commands =
	parseInput commands
	|> List.map toFunc
	|> List.fold (fun position command ->
	position >>= move command obstacles)
	(Ok position)
	|> formatOutput

view raw Execution of commands hosted with ❤ by GitHub

I decided that I will not use the "M-word" in this article but you can see that monads are not so scary after all.

The only thing left is to show the implementation of the formatOutput function:

	let formatOutput result =
	let toStr p =
	sprintf "%O:%O:%O" p.location.x p.location.y p.direction
	match result with
	| Ok p -> toStr p
	| Error p -> toStr p |> sprintf "O:%s"

view raw Output formatting hosted with ❤ by GitHub

We implemented all the requirements, but there is one more thing to mention. The actual signature of the execute function doesn't match the required signature:

	seq<char> -> string //Required execute signature
	RoverPosition -> Location list -> seq<char> -> string //Actual execute signature

view raw Execute signature hosted with ❤ by GitHub

There is a good reason for that and we will cover it in the next post.