Wednesday, December 4, 2019

Functional Mars Rover kata: Domain modeling

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:

type Coordinate =
| One
| Two
| Three
| Four
| Five
| Six
| Seven
| Eight
| Nine
| Ten
view raw Coordinate hosted with ❤ by GitHub
type Direction =
| North
| South
| East
| West
view raw Direction hosted with ❤ by GitHub
type Command =
| RotateLeft
| RotateRight
| Move
view raw Command hosted with ❤ by GitHub
For the "AND" types we are going to use records:

type Location = {
x: Coordinate
y: Coordinate
}
view raw Location hosted with ❤ by GitHub
type RoverPosition = {
location: Location
direction: Direction
}
view raw RoverPosition hosted with ❤ by GitHub
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 matchingAlso, 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):

let generateCoordinateSuccessor coordinate =
match coordinate with
| Coordinate.One -> Coordinate.Two
| Coordinate.Two -> Coordinate.Three
| Coordinate.Three -> Coordinate.Four
| Coordinate.Four -> Coordinate.Five
| Coordinate.Five -> Coordinate.Six
| Coordinate.Six -> Coordinate.Seven
| Coordinate.Seven -> Coordinate.Eight
| Coordinate.Eight -> Coordinate.Nine
| Coordinate.Nine -> Coordinate.Ten
| Coordinate.Ten -> Coordinate.One
let generateCoordinatePredecessor coordinate =
match coordinate with
| Coordinate.Ten -> Coordinate.Nine
| Coordinate.Nine -> Coordinate.Eight
| Coordinate.Eight -> Coordinate.Seven
| Coordinate.Seven -> Coordinate.Six
| Coordinate.Six -> Coordinate.Five
| Coordinate.Five -> Coordinate.Four
| Coordinate.Four -> Coordinate.Three
| Coordinate.Three -> Coordinate.Two
| Coordinate.Two -> Coordinate.One
| Coordinate.One -> Coordinate.Ten
Next, we define the transitions for the rotation in the same manner:

let rotateLeft direction =
match direction with
| Direction.North -> Direction.West
| Direction.South -> Direction.East
| Direction.East -> Direction.North
| Direction.West -> Direction.South
let rotateRight direction =
match direction with
| Direction.North -> Direction.East
| Direction.South -> Direction.West
| Direction.East -> Direction.South
| Direction.West -> Direction.North
view raw Direction hosted with ❤ by GitHub
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:

let calculateNewCoordinates position =
let location = position.location
let newLocation =
match position.direction with
| Direction.North ->
{ location with y = generateCoordinateSuccessor location.y }
| Direction.South ->
{ location with y = generateCoordinatePredecessor location.y }
| Direction.East ->
{ location with x = generateCoordinateSuccessor location.x }
| Direction.West ->
{ location with x = generateCoordinatePredecessor location.x }
{ position with location = newLocation }
let rotateLeft position =
{ position with direction = rotateLeft position.direction }
let rotateRight position =
{ position with direction = rotateRight position.direction }
In the next article, we are going to implement the execution of a command sequence and explore the error handling mechanisms in functional programming.