Solving the Mars Rover Kata with a Free Monad in Purescript
We want to be able to describe what it means to move our rover without caring whether the implementation is just in memory or there’s an actual rover millions of miles away reacting to our commands.
I’ve wanted to play with Purescript for some time now but couldn’t decide on a project. I wanted something that was small enough to finish in a couple sittings but would still showcase some of the language features. That’s when I saw the following tweet:
The kata is quite simple: given a starting point, move around a 10 x 10 grid with Forward, Backward, Left, and Right commands. I’ve worked through the kata several times, generally with the idea of doing TDD, but when I saw this tweet I immediately wanted to try writing the kata as a pure functional program in Purescript.
Modeling State without going to 11
The first thing I wanted to do was to model the state that we need to keep. We’ll need to know the
y coordinates of our rover and the direction it is heading. It was very tempting to model the coordinates as
Int values, but our constraints are very clear that it is a 10 x 10 grid which means if we modeled the
x coordinate as an
Int we’d be able to write and compile code that expressed our rover’s
x position at 11 which is nonsense on our 10 x 10 version of Mars. Instead, I opted to create a sum type containing all possible coordinates
We also create another sum type for
Direction and then define a record type
State which manages all of our rover’s state in a single type. While our definition of
Coord was verbose, it ensures that every inhabitant of our
State type is valid. Said another way, every value of the
State type that can be created is a valid place and heading on the surface of Mars.
Defining our commands
From the kata definition we know that there are 4 commands that we can send to our rover:
Right. We can’t mutate state or have instance methods because our language doesn’t allow it, so signatures that involve
void don’t exist. If we think about the type signature for each command, we can see that they’re all identical. Each takes a
State value and returns a new
State -> State. Here’s an example of the implementation function that turns the rover left:
We simply pattern match over the current direction and return a new
State value with it’s direction changed. The other implementations all follow from this basic structure.
Creating our Domain Specific Language
Now that we can see that all of our commands are the same type
State -> State, we want to create a DSL that will allow us to describe programs as data so that we can separate the implementation from the intent. We want to be able to describe what it means to move our rover without actually caring whether the implementation is just in memory or there’s an actual rover millions of miles away reacting to our commands.
Our first step is to define a sum type for our DSL so that our programs become data. It turns out that’s pretty simple in this case because we only have 4 commands. Here’s our first take at a DSL:
Great, so we know that whatever program we create with
Dsl can only use one of the 4 commands. Unfortunately, our structure is incomplete for a few reasons:
- We know that to successfully issue a
Forwardcommand will require us to know about the current
- We know that once a command runs we’ll receive a new
Statevalue so we’ll need to encode that somehow as well.
- We want to be able to sequence commands. i.e. Go Left, then Forward, then turn Left.
- We want to be able to combine multiple commands into a single command. For instance, we may want to combine two
Leftcommands in sequence into a program called
TurnAroundand then be able to use the
TurnAroundprogram inside of any other programs written with
To solve those problems with our first try at our
Dsl we’ll enlist some help from an external library by running
bower install purescript-free. In the following example, note how the function signature aligns with the types in our
Once we have our
DslF a defined we can then turn our Dsl into a monad for free by calling
type Dsl = Free DslF.
Don’t be afraid of the added type parameter
a. What this means is that any value that we can create of
Dsl describes a program that, when run, will produce an
a. At this point we have no idea what kind of program someone might create with our
Dsl so we keep the
a completely generic so that the person writing programs with our
Dsl can decide.
Providing some helper functions
Now that we have our
Dsl we’ll want programs to use it rather than our
DslF directly. The problem is that
Free has no knowledge of our specific union cases defined in
DslF. We can fix that with a handy function from
liftF which effectively lifts our
DslF type into a
If we hadn’t used
liftF we’d have a
State -> DslF a function. By using
liftF we’re able to return a value of
Dsl a from the function, and because our final argument to
Forward is the
identity function we know that it’s a
Some simple programs
Now that we have some helper functions to create values of
Dsl we can create programs that satisfy all of our 4 concerns from earlier. Because
Dsl is a monad we can simply chain instructions together with
>>= to build more complex instruction sets while still always creating values of
We can now arbitrarily slice functionality into chunks because everything composes together. The
turnAround function composes two
left instructions to create a new instruction which is then easily inserted into the chain inside of
Interpreting our structure
All of the code we’ve written so far allows us to build program instructions. We still need to interpret those instructions in some way. The main benefit to separating our Intent from our Implementation is that any program written in our
Dsl can be interpreted by any interpreter of our
If we wanted to simply log to the console in our interpreter (which we’ll do in a moment), we could write an interpreter from
Dsl ~> Effect using Purescript’s
Effect type. If we wanted an interpreter to issue http calls on every step (which could fail), we could write an interpreter from
Dsl ~> Aff using the asynchronous effect type because
Aff handles the effect of asynchronous processing that may fail.
Logging to the console
Logging to the console is an effectful computation and because Purescript manages effects, we want to be able to turn any
Dsl a into an
Effect a that can be executed by the Purescript runtime. This sort of transformation is called a Natural Transformation and it’s common enough that Purescript has the
~> syntax to describe it. We’ll use another helper from
foldFree which will allow us to write our interpreter quite succinctly.
interpretDsl function is a Natural Transformation (for all possible types
a, it transforms a
Dsl a into an
Effect a), but basically
foldFree does all of the heavy lifting. It takes a Natural Transformation
morph as its argument. All we have to do is interpret each effect as we’d like. In this case we’re just getting the new
State of our rover in accordance with the instruction, logging it, and passing the updated
State to the
next function in the chain.
Putting it all together
We now have all of the pieces to run an application and see the results in the console. We apply an initial
State value to our
program function to get a value of
Dsl State. We can then apply that value to our
interpretDsl function to move our rover through the instruction set and log its position at each step. Because the result of applying
program is a
Dsl State, the
s value in line 18 is a
This approach takes a bit more code than simply coupling intent and implementation, but it has several big wins
- Illegal states are unrepresentable through our use of sum types describing the rover’s
- We have completely described what it means to move a rover according to the kata description.
- A program written in our
Dslcan’t do anything outside of what was defined in the kata description because it can only use or combine the 4 initial commands.
- Any program written in our
Dslcan be interpreted by any interpreter of our
The full source is available here https://github.com/reidev275/FreeMarsRover
See anything I could do better? Post a comment to let me know!
You may also be interested in the following: