Game of life in Haskell

The Game of Life kata is a reference problem that can be solved many different ways, to experience a new language, methodology, testing framework, IDE, or else. Keeping the problem fixed while changing one factor into the equation lets you avoid many (but not all) confounding variables.

I had the suspect that functional implementations of the Game of Life would be very concise, having the problem a mathematical formulation. After some functional PHP code , this time I tried Haskell, a famous statically typed functional language.

The basic types

In Haskell, we can define enumerative data types. The state of a cell in the Game of Life can be modelled with a boolean, or more precisely with any type containing just two values. So it makes sense to give names to the possible states instead of using True and False.

data CellState = Dead | Alive

More complex data types can be built by composing a list of existing types. On the right side of = Position is a constructor that specifies this "Value Object" is composed by 2 Integers, representing in fact the position of a cell in the infinite 2D plane.

data Position = Position Integer Integer

Functions also have types: I define a Generation as a snapshot of the plane at one moment in time. A way to fully describe a generation is of providing a function that maps each possible instance of Position to a CellState, either Dead or Alive.

type Generation = Position -> CellState

Leaf functions

I don't know if there's a technical term, but even while developing outside-in we have to arrive at some functions that do not call other ones.

is_alive is a simple map from a CellState to a boolean value; we need it because primitives like filter need a Bool as an input (more precisely as the return type of the function taken as an input):

is_alive :: CellState -> Bool
is_alive Alive = True
is_alive Dead = False

neighbors is capable of generating a list of Position values from a single one, a list of 8 values actually. I didn't find a simpler solution than generating it by hand, but this case-based definition can be probably shortened:

neighbors :: Position -> [Position]
neighbors (Position x y) =
  [(Position (x-1) (y-1)), (Position x (y-1)),  (Position (x+1) (y-1)), (Position (x+1) y),
  (Position (x+1) (y+1)), (Position x (y+1)), (Position (x-1) (y+1)), (Position (x-1) y)]

Composing

The alive_neighbors function takes a Generation and a Position, and it tells you how many of the 8 cells near to the chosen Position are Alive in that Generation.

alive_neighbors :: Generation -> Position -> Int
alive_neighbors generation position = length (filter is_alive (map generation (neighbors position)))

Reading the function from the inside: first neighbors is applied to the Position, and generation is mapped on the result: at that point we have a list of CellState values. filter produces a new list containing only Alive values, and length counts them.

You can notice in the type signature how a multiple-argument function is specified, by separating arguments and the return type with ->:

alive_neighbors :: Generation -> Position -> Int

The reason is due to currying as each function in Haskell has only one argument, and what we are writing is a function that takes a Generation and returns a functon that takes a Position. But this is not important right now: this notation just means we have two arguments, and the returned value will be an Int.

Right now we are ready to solve the full problem: our evolution function takes a Generation and produce another Generation. It's an higher-order function like map and filter, because it takes a lower-level function as an argument instead of just using it.

evolution :: Generation -> Generation
evolution generation position =
  case (alive_neighbors generation position) of
  2 -> if (is_alive (generation position)) then Alive else Dead
  3 -> Alive
  _ -> Dead

Here the magic of currying happens. The type signature for evolution can be read as:

evolution :: Generation -> Position -> CellState

So in order to "return" a new Generation from an old Generation we can define a function that takes the old Generation and a Position as inputs and returns a CellState. Seems magic, but it's really consistent.

The rest of the function is just a switch statement, returning the new state as Alive or Dead depending on the current CellState and the number of alive_neighbors.

Displaying

Since I do not know yet how to write unit tests (or property-based tests) in Haskell, the only way to experiment with my implementation while coding was to visualize the results.

These functions take a Generation and visualize it in a 10x10 grid starting at the (1, 1) coordinates.

visualize_generation generation =
  map (visualize_line generation) [1..10]

visualize_line :: Generation -> Integer -> String
visualize_line generation y =
  concat (map (visualize_cell generation y) [1..10])

visualize_cell generation y x =
  case (generation (Position x y)) of
  Alive -> ['X']
  Dead -> [' ']

Here is the classic bar structure, a sequence of three alive cells that rotates by 90° at each new Generation:

bar (Position 1 2) = Alive
bar (Position 2 2) = Alive
bar (Position 3 2) = Alive
bar (Position x y) = Dead

Here is the bar rotating:

*Main> mapM_ print (visualize_generation bar)
"  "
"XXX  "
"  "
"  "
"  "
"  "
"  "
"  "
"  "
"  "
*Main> mapM_ print (visualize_generation (evolution bar))
" X  "
" X  "
" X  "
"  "
"  "
"  "
"  "
"  "
"  "
"  "
*Main> mapM_ print (visualize_generation (evolution (evolution bar)))
"  "
"XXX  "
"  "
"  "
"  "
"  "
"  "
"  "
"  "
"  "

Conclusions

Functional approaches sometimes are much faster. I would like currying with no syntax overhead to be available in imperative languages, to easily transform method calls into closures.

Haskell syntax in fact match the functional style very well. Its programs usually run correctly, the moment you can get them to compile.