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.

Photo by Jared Evans on Unsplash

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 x and 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 One through Ten.

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: Forward, Backward, Left, and 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 value. 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:

  1. We know that to successfully issue a Forward command will require us to know about the current State value.
  2. We know that once a command runs we’ll receive a new State value so we’ll need to encode that somehow as well.
  3. We want to be able to sequence commands. i.e. Go Left, then Forward, then turn Left.
  4. We want to be able to combine multiple commands into a single command. For instance, we may want to combine two Left commands in sequence into a program called TurnAround and then be able to use the TurnAround program inside of any other programs written with Dsl.

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 DslF cases.

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 Control.Monad.Free called liftF which effectively lifts our DslF type into a Dsl.

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 Dsl State.

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 Dsl State.

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 outAndBack.

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 Dsl.

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 Control.Monad.Free called foldFree which will allow us to write our interpreter quite succinctly.

Our 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 initial to program is a Dsl State, the s value in line 18 is a State value.

This approach takes a bit more code than simply coupling intent and implementation, but it has several big wins

  1. Illegal states are unrepresentable through our use of sum types describing the rover’s State.
  2. We have completely described what it means to move a rover according to the kata description.
  3. A program written in our Dsl can’t do anything outside of what was defined in the kata description because it can only use or combine the 4 initial commands.
  4. Any program written in our Dsl can be interpreted by any interpreter of our Dsl

The full source is available here

See anything I could do better? Post a comment to let me know!

You may also be interested in the following:

Separating Intent from Implementation in Typescript