Conway's Game of Life: Scala Edition with Zippers
by Rebecca Mark- •
- December 13, 2019
- •
- scala• functional programming• functional
- |
- 13 minutes to read.
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.
Comonads, in Context
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] = {
new 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.
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)
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.
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.
With gratitude to: