A Scala Functional Conway’s Game of Life

A couple weekends ago, I participated in a Global Day of Coderetreat event in Boulder, CO. Coderetreat is an all-day event where developers can practice techniques like pair programming, Test Driven Development, and simple design, while working with peers on a common problem. The canonical problem for Coderetreat events is Conway’s Game of Life, which has a nice size – not too simple and not too complex.

The participants in Boulder this year skewed towards Ruby and Javascript, but were very interested to try out Scala, so I did most of the day’s sessions (4 out of 5) in Scala. Most of these approaches skewed towards the object-oriented side of Scala, usually using algebraic data types with polymorphism to represent the possible states of cells in the simulation. With the final session of the day, my partner and I were able to tackle a more purely functional approach.

We started from a high-level test, using some well-known shapes – the block and the blinker, and then dove into lower-level tests for the individual steps in the algorithm. We knew we wanted to be based on transformation of a list of live cells, and that each cell would keep its own position but not directly track its neighbors, and that we would not have a direct notion of a “board” or “grid”, just keeping that information discoverable from the positions and the live list. We made pretty good progress generating the list of neighbors and augmenting the live list with this information.

I redid this approach and put the results up on github. It took me more than the allotted 45 minutes, but not more than about double that. The basic algorithm I used is:

  1. Start with a list of live cells. Each cell is basically just a position, because we know they are all alive
  2. Generate the list of all surrounding cells. These are the cells that may come to live due to the reproduction rule.
  3. Combine the two lists, removing duplicates
  4. For each cell in this list of candidate cells, determine if it is alive (it was in the list of live cells) and count its neighbors
  5. For each cell in the list, apply the rules (based on current state and neighbor count) to decide if it should live or die
  6. Filter the list to just the ones that live

Step two is a flatMap, applying a function to generate neighbors. Step 4 is a map of the neighbor count and liveness check. Step 5 becomes the predicate used to filter in step 6. This whole sequence then becomes a function from one generation to the next generation, both expressed as lists of live cells.

While I found this interesting from a functional purity perspective, I didn’t feel like this was so successful from the TDD perspective. I never really felt like the tests were driving this approach. Nothing in the high-level tests encouraged us to use this algorithm, apart from the initial decision to represent the shapes as lists of live cells. These high level tests also didn’t really guide us in what to do first to make this work, so we very quickly moved to using lower-level tests. These tests helped us to make sure the result of a transformation were right, but we didn’t feel any particular guidance or pressure to tell us whether a transformation was inherently a map, filter, fold, or some other combinator. These tests were useful to help us make sure our solution worked in small pieces, but didn’t give us much vision of how the pieces would go together.

To be fair, we did start with an algorithm approach in mind, so trying to write tests to drive us in that direction was different from starting with less bias. We definitely did refactor much in this approach. Perhaps if we had started with something more like an “evil implementor” approach, where we direcly recognized shapes and returned canned responses, we might have arrived at a solution more organically.

Almost all my TDD experience has been in a more object-oriented context, so I’m more accustomed to thinking in those terms when seeing where a test drives the implementation. Perhaps as I gain more experience using tests to drive to functional solutions, I will understand better how tests guide a functional approach. As with other aspects of functional programming, there is a different way of thinking and approaching problems, that will likely play out in TDD as well.



Scala Options and Sudoku

Scala Options are a nice alternative to null values. They force us to consider the None case explicitly, rather than hiding in documentation, for example, the fact that a method can return null in some circumstances. They also tie in nicely to chained behavior, so that a sequence of operations that produce a None along the way can collapse to just the None, similar to constructs such as Groovy’s elvis operator ?:.

I have been working through a sudoku solver as a Scala learning project. This solution is based on constraint propagation – eliminating possibilities and placing values in a mutually recursive relationship – and search, as described in Peter Norvig’s article. I wanted to distinguish between valid puzzle states (some or all values placed in the grid, but no conflicts) and contradictory states (trying to place a value in a position where it is not possible), using a construct in the type system, rather than using null as might be done in Java.

I thought an Option would be a good choice for this:

def placeConjecture(row:Int, col:Int, conjecture:Int):Option[SudokuGrid]

Placing a conjecture returns a new SudokuGrid with updated values, wrapped in an Option. If the conjecture is possible, Some(newgrid) is retured, but if the conjecture leads to a contradiction, None is returned.

To build up a puzzle, for example establishing the starting state or just setting up a scenario for testing, it is necessary to place multiple conjectures. Without Option, we’d use something like:


With option, we have to account for the possibility of one of these placeConjecture calls returning None. The Option object of course doesn’t have the placeConjecture method, so we need to extract the contained SudokuGrid in the case of Some(grid), or short-circuit and return None for the whole chain.

Having no idea how to go about this, I started with a simple case for tests:


This obviously doesn’t handle propagation of the None value. For setting up some tests when I knew that no contradictions would arise, this sufficed, but was far from ideal.

One nice feature of Option, is that as a monad (not that I completely understand the concept; have no fear that a monad post is coming), it can be used in a for comprehension. In this case, the chain of Options get passed through, evaluating to the final result when all the Options are Some() and short-circuiting to None if any of them are None. So my attempt to use a for comprehension with this sequence looked something like this:

for {
    a <- empty.placeConjecture(0,0,5)
    b <- a.placeConjecture(3,5,7)
    c <- b.placeConjecture(2,6,1)
} yield c

This works fairly well for small examples like above, but it gets unwieldy quickly. It also doesn’t allow (at least, not that I could figure out) use of a generator to generate some of the values. I wanted to be able to place conjectures (or equivalently, eliminate possibilities) for a number of cells at once, and needed to determine how to make the results from one iteration carry into the next iteration, ideally without using a var.

After banging my head against this for a bit, I realized I was using the wrong approach. Rather than for comprehension, what I was really doing was combining results across a list – folding!

    (gridopt,(row,col,conjecture)) => gridopt match {
        case None => None
        case Some(grid) => grid.placeConjecture(row,col,conjecture)

The starting list contains the conjectures I want to place. Starting with an empty SudokuGrid, the combination function calls the placeConjecture method on Somes, passing the result on to the next iteration. When None is encountered, this gets passed the rest of the way along.

This approach then combines well with generating the list programmatically:

val thelist = for (i <- 1 to 8) yield i
    (gridopt,poss) => gridopt match {
        case None => None
        case Some(grid) => grid.eliminatePossibility(0,0,poss)

In the end, I decided that layering my semantics on top of Option wasn’t quite as expressive as I would like. Specifically, this approach means that the calling code needs to know that None means a contradictory puzzle state. I instead created an algebraic type with LiveSudokuGrid subclasses for non-contradictory states and a ContradictorySudokuGrid object subclass for contradictory states. By implementing placeConjecture and eliminatePossibility appropriately for the subtypes I can propagate the contradictory result across further calls. At some point I’ll try to make these monadic as an exercise, but that’s for another post!