47 Degrees joins forces with Xebia read more

# Conway's Game of Life: Scala Edition with Zippers

This article is part of our series on Functional Programming solutions for the Global Day of Coderetreat challenge. This project was co-authored by Kate Fulton, a Software Engineer at Amplero and friend of 47 Degrees.

In celebration of this year’s Global Day of Coderetreat, we created an implementation of Conway’s Game of Life in Scala which showcases abstractions from functional programming.

In particular, our implementation makes use of the lesser-known dual of the Monad: the Comonad. You might have heard of monads before in contemporary FP parlance - we think they’re pretty cool. In functional programming, it’s common for structures or patterns like monads to have a corresponding concept that operates like its mirror image. We’ll give an example of how comonads can be encoded in Scala via type classes and see how they end up being useful for the Game of Life in a little bit.

Today, we’d love for you to take away an understanding of comonads and maybe some inspiration for your very own Game of Life implementation.

Rather than getting lost in metaphors (if a monad is a burrito, is a comonad eating the burrito?), let’s start with building an intuition for the shape of a comonadic computation and think about when it might be useful.

While Monads are useful for chaining functions that produce a value in a context, Comonads are useful for executing a query or series of queries over a given context to produce a value. A simple example of this is rolling averages. Say we have a stream of integers and we want to track the average of a window of values as we traverse the data structure. We are able to leverage the comonadic properties of that stream to extract the neighboring values from the stream and apply them to that moving average. In short, comonads are broadly used for computations where global context (a never-ending stream of integers) is useful for computing a value locally (the rolling average).

Now that we have an intuition of what a Comonad might be used for, we still need a way to specify when a datatype has a comonad instance. In Scala, we have a variety of libraries available to support these functional programming abstractions, but for the sake of exposition, we’ll be creating our own type class.

First, we’ll define our Comonad trait.

``````trait Comonad[W[_]] extends Functor[W] {
def extract[A](w: W[A]): A
def duplicate[A](w: W[A]): W[W[A]]
def coflatMap[A, B](w: W[A])(f: W[A] => B): W[B] = ???
}
``````

You might notice that category theorists have a sense of humor. `W` is commonly chosen as the name for the type constructor on Comonads because it’s Monad’s `M` flipped upside-down.

`extract` (sometimes called `counit`) is a function that takes some context W[A] and allows us to get a value of type A from that context. Its corresponding function in the land of Monads is `pure`, which injects, or “lifts,” a value into an effectful context.

`duplicate` (aka `coflatten`) is a function that takes one layer of context and returns two.
It replaces every value in the original data structure with the value alongside its surrounding context. This is the inverse of the ability that monads have to “flatten” or collapse layers of context down to one.

`coflatMap` is what supports composing functions that consume context and produce a transformed value in that context. Compare coflatMap’s function signature for f, `W[A] => B` to flatMap’s `A => M[B]` and you’ll see a glimpse of what we mean when we say the arrows are reversed for co-constructions.

Every comonad is also a functor, so, when we implement the comonad instance for our data types, we’ll also be creating a map function.

### Things to ponder

1.) Can you define a Comonad over standard Scala Options or Lists? Why or why not? Answer

2.) The signature for `map` can be written `def map[A, B](fa: W[A])(f: A => B ): W[B]`. How might you derive the implementation for coflatMap from `duplicate` and `map`? Answer

3.) What happens if we pass `extract` as the function `f` in our coflatMap method? Answer

## The Game of Life

First, let’s focus on how we might represent the cells in the grid. As we’ve seen in the Swift implementation, we can represent the grid as a `Store` of coordinates, and in the Haskell implementation, we can represent the grid as a function that maps coordinate points to the cell status. Another way we can model this domain is by creating our own collection-like comonadic data type. We know we’ll need a non-empty structure, and because the Game of Life rules involve peeking at your neighboring values to determine overpopulation or underpopulation, we’ll need to easily look at adjacent values.

### Enter the Zipper!

One data structure that fulfills these requirements is a `Zipper`.

``````case class Zipper[A](left: Stream[A], focus: A, right: Stream[A])
``````

A Zipper has a focus value, and a stream of values to the left and right of that focus. To get at the neighboring values, we’ll need to implement two functions on the Zipper class, moveLeft and moveRight - these functions re-focus the Zipper on the value to the left and right of the current focus, respectively. Caveat

``````def moveRight: Zipper[A] = {
if (right.isEmpty) this
else Zipper(focus #:: left, right.head, right.tail)
}

def moveLeft: Zipper[A] = {
if (left.isEmpty) this
else Zipper(left.tail, left.head, focus #:: right)
}
``````

As you might have guessed, Zippers have a comonad instance, which we can implement like so:

``````implicit def zipperComonad: Comonad[Zipper] = new Comonad[Zipper] {
override def extract[A](w: Zipper[A]): A = w.focus

override def duplicate[A](w: Zipper[A]): Zipper[Zipper[A]] = {
Zipper(w.duplicateLefts, w, w.duplicateRights)
}

override def map[A, B](fa: Zipper[A])(f: A => B): Zipper[B] = {
Zipper(fa.left.map(f), f(fa.focus), fa.right.map(f))
}
}
``````

The `extract` method simply inspects the current focus of the zipper, but `duplicate` is a little trickier. Duplicate creates a Zipper of Zippers where every element is in the focus position once. The focus of this wider zipper is the current zipper, but we also need to build left and right streams of Zippers with shifted foci. One way we can accomplish this is using a handy function for building up recursive data structures called `unfold`.

``````def unfold[A, B](a: A)(f: A => Option[(B, A)]): Stream[B] = f(a) match {
case Some((b, a)) => b #:: unfold(a)(f)
case None         => Stream.empty
}
``````

We then use unfold to build a stream of zippers in which we’ve successively shifted the zipper focus to the left or right, until there are no more elements.

``````def duplicateRights[B]: Stream[Zipper[A]] = unfold(this)(z => z.maybeRight.map(x => (x, x)))
``````

With one Zipper, we can model the X-axis of our Game of Life. By creating a Zipper of Zippers, we can create the desired 2-dimensional grid representation. The focus of the outer zipper locates a point in the Y-axis, and the focus of the inner Zipper locates a point in the X-axis.

Let’s define a case class to contain our Zipper of Zippers.

``````case class GridZipper[A](value: Zipper[Zipper[A]])
``````

We can leverage our earlier `moveLeft` and `moveRight` functions to get the neighboring cardinal directions of any focus point in the grid.

``````def north: GridZipper[A] = {
GridZipper(value.moveLeft)
}

def south: GridZipper[A] = {
GridZipper(value.moveRight)
}

def east: GridZipper[A] = {
GridZipper(value.map(xAxis => xAxis.moveRight))
}

def west: GridZipper[A] = {
GridZipper(value.map(xAxis => xAxis.moveLeft))
}
``````

We’ll need to inspect the values when we’re walking the neighborhood, and for that, we can use the `extract` method from the comonad instance for the grid. Let’s add that now.

``````implicit def gridZipperComonad: Comonad[GridZipper] = {
override def extract[A](w: GridZipper[A]): A = w.value.focus.focus

override def duplicate[A](w: GridZipper[A]): GridZipper[GridZipper[A]] = map(GridZipper(nest(nest(w.value))))(GridZipper(_))
}
}
``````

We now have what we need to model the logic of the game’s successive generations. Let’s write a function to gather a cell’s immediate “neighborhood” of values.

``````def getNeighbors: List[A] = {
List(
this.north.extract,
this.east.extract,
this.south.extract,
this.west.extract,
this.north.east.extract,
this.north.west.extract,
this.south.east.extract,
this.south.west.extract
)
}
``````

Now let’s encode the overpopulation and underpopulation logic using this method. We’re going to assume our GridZipper contains Integers that are either a 1 or a 0, representing the alive or dead state for easy summation logic.

``````def cellLifecycle(grid: GridZipper[Int]): Int = {
val neighbors = grid.getNeighbors
(neighbors.sum, grid.extract) match {
case (sum, 1) if sum == 2 || sum == 3 => 1
case (3, 0) => 1
case (_, 1) => 0
case (_, x) => x
}
}
``````

To represent a generation in the Game of Life, we want a function that takes in our grid and creates a new GridZipper where every cell is evaluated by our cellLifecycle function.

``````def desiredFunction(initialGridState: GridZipper[Int])(nextCellState: GridZipper[Int] => Int): GridZipper[Int]
``````

Our desired next generation function is none other than `coflatMap`, which we earlier derived from our `duplicate` and `map` functions.

## Zipping it all together

What remains to be done is setting our initial board state and kicking off the game. To do that, we made a small console app for users to place common patterns in the Game of Life at particular coordinates. First, we `createCoordinateLists` by taking the cross-product of a range from zero to our desired width, grouping it by the width to create a grid-like structure of coordinates. Then we translate the lists of coordinates into a GridZipper using the `fromLists` function to transform our plain Scala lists. From our `GridZipper[Coordinates]`, we can use the map function we defined for our GridZipper to transform each coordinate pair into a 0 or 1 depending on whether that point exists in the user’s desired initial board.

``````def buildGrid(setCellValue: Coordinates => Int, width: Int): GridZipper[Int] = {
val coordinates: List[List[Coordinates]] = createCoordinateLists(width)
val gridZipperCoordinates: GridZipper[(Int, Int)] = GridZipper.fromLists(coordinates)
gridZipperCoordinates.map(setCellValue)
}
``````

For rendering, we make use of Fs2 with Cats-effect, streaming the generations of the game to the console with an appropriately throttled frame rate.

The full implementation of the Game of Life using Zippers can be found at Comonadic Life. We hope you find it edifying and entertaining!

Our goal in writing the Game of Life and this subsequent post in the series is far from being prescriptive or final. Of course, we hope to impress upon you that there is power in knowing about functional concepts, and that through their application we are able to solve complex problems in an elegant and clear manner. But there are perhaps as many ways to tackle the Game of Life as there are emergent phenomena to be found in the game itself. Moreover, as you’ll have seen by the Swift, Haskell, and Kotlin implementations by my illustrious coworkers, every one of them brings a unique and beautiful set of permutations into succession.

## Appendix

1.) Not all “containers” have a comonad instance! Standard Scala Options and Lists have an empty case, which prevents us from implementing `extract`. In those cases, we can’t get something from nothing. Interesting note: Option and List can, however, implement a weaker abstraction in the Cats typeclass hierarchy, CoflatMap.

Back

2.) For reference, the signature of coflatMap is `def coflatMap[A, B](w: W[A])(f: W[A] => B): W[B]` The functions we’ll need to implement this are duplicate: `def duplicate[A](w: W[A]): W[W[A]]`, and map, which we get for free because any Comonad over W[_] has a functor instance for W[_] as well: `def map[A, B](fa: W[A])(f: A => B ): W[B]`

First, let’s duplicate w: `val duplicated: W[W[A]] = duplicate(w)`

And because coflatMap takes a function `f` that operates on W[A] and returns some B, we can take our value `duplicated`, map over it applying the function `f` to consume one layer of context, and return a W[B]. ` val wb: W[B] = map(duplicated)(f) `

Simplified, this is: `def coflatMap[A, B](w: W[A])(f: W[A] => B): W[B] = map(duplicate(w))(f)`

Back

3.) If we pass `extract` as the function `f` in our coflatMap method, we should get our original value back! Indeed this is something that must be true in order for a data structure to have a valid Comonad instance.

Back

4.) Intrepid readers might note that if the `moveLeft` or `moveRight` functions encounter the end of the stream, they’ll return the current zipper. This can cause odd behavior when the cells at the edge of the grid are flipped alive. While the Game of Life is theoretically played on an infinite grid, we typically represent it in a space no larger than our computer screens. One way we can account for this is by changing the Zipper data structure slightly.

``````case class Zipper[A](left: Stream[Option[A]], focus: Option[A], right: Stream[Option[A]])
``````

While we’re no longer able to get a valid `extract` from this data structure due to the focus being optionally present, we can still implement `duplicate` and `coflatMap`, making this data structure have a `CoflatMap` type class instance.

Back

With gratitude to:

## Ensure the success of your project

47 Degrees can work with you to help manage the risks of technology evolution, develop a team of top-tier engaged developers, improve productivity, lower maintenance cost, increase hardware utilization, and improve product quality; all while using the best technologies.