In the following article series, we are going to explore a functional approach to the Mars Rover kata. It is a well-known kata and you can find a lot of different solutions implemented in object-oriented programming languages like Java or C#. We are going to use F# for our implementation. Even if F# is a multi-paradigm programming language, the goal is to implement the kata in a purely functional manner.
The rules of the Mars Rover kata are:
- You are given the initial starting point (1,1, N) of a rover.
- 1,1 are the X, Y coordinates on a grid of (10,10).
- 'N' is the direction it is facing (i.e. N, S, E, W).
- 'L' and 'R' allow the rover to rotate left and right.
- 'M' allows the rover to move one point in the current direction.
- The rover receives a character array of commands e.g. RMMLM and returns the finishing point after the move e.g. 2:1:N.
- Implement wrapping from one edge of the grid to another (planets are spheres after all).
- The grid may have obstacles. If a given sequence of commands encounters an obstacle, the rover moves up to the last possible point, aborts the sequence and reports the obstacle e.g (O:2:2:N).
The first step after the initial domain analysis should be to create domain types. The great thing about F# is that it has a built-in algebraic type system. That means that we can build new types from smaller types using composition. The composition of types is possible by "AND-ing" or "OR-ing" them together. With that approach, we can define the following domain types:
Coordinate: One OR Two OR Three...OR Ten.
Location: X coordinate AND Y coordinate.
Direction: North OR South OR East OR West.
Rover position: Location AND Direction.
Command: Rotate left OR Rotate right OR Move
The specified domain types are easy to implement with the F# type system.
The "OR" types are implemented with discriminated unions:
For the "AND" types we are going to use records:
Coordinate: One OR Two OR Three...OR Ten.
Location: X coordinate AND Y coordinate.
Direction: North OR South OR East OR West.
Rover position: Location AND Direction.
Command: Rotate left OR Rotate right OR Move
The specified domain types are easy to implement with the F# type system.
The "OR" types are implemented with discriminated unions:
For the "AND" types we are going to use records:
Rover's movement can be modeled as a sequence of states. A state transition can be generated from an input command and the current state of the rover. This is known as a state machine. The interesting thing about discriminated unions is that we can observe each case of a union as a state. We already implemented the needed states, so the next step should be to define the state transitions. For the implementation of the state transitions, we are going to use pattern matching. Also, this is a good opportunity to express "Implement wrapping from one edge of the grid to another (planets are spheres after all)" requirement. We can do this with the explicit state transitions (Coordinate.Ten -> Coordinate.One and Coordinate.One -> Coordinate.Ten):
Next, we define the transitions for the rotation in the same manner:
Next, we define the transitions for the rotation in the same manner:
With the appropriate types and transitions in place, we can finally define functions that are going to generate the next position from the current position of the rover:
In the next article, we are going to implement the execution of a command sequence and explore the error handling mechanisms in functional programming.