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:

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:

Signature of the toFunc function is:

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

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:

Signature of the move function is:

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:

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:

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:

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

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:

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:

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