# Conway's Game of Life using Kotlin and Arrow

- by Jorge Castillo
- •
- December 12, 2019
- •
- kotlin• functional programming• arrow

*This article is part of our series on Functional Programming solutions for the Global Day of Coderetreat challenge. Feel free to take a look to our other posts in the series, where we solve the problem using Swift and Haskell.*

The Global Day of Coderetreat asked participants to solve the Conway’s Game of Life challenge using various languages. In this post, we’ll showcase a basic approach for it using Kotlin and Functional Programming provided by the Arrow library.

When I looked at this problem, the first thought that came to my mind was an **evolving program state**. I decided to use this opportunity to showcase the `State`

Monad a bit, and, more specifically, the `StateT`

Monad Transformer. But, first things first, let’s take a look at our problem domain.

## Modelling our domain

If you read the problem description, you’ll notice we are going to need some cells. Given a `Cell`

is restricted to having only one of two possible types, we can use a Kotlin `sealed class`

to model it.

```
sealed class Cell {
abstract val id: String
data class Alive(override val id: String) : Cell() {
constructor() : this(generateId())
}
data class Dead(override val id: String) : Cell() {
constructor() : this(generateId())
}
}
```

We give each cell a different identity so we can differentiate them and compare using equals if required in tests. Since `data classes`

in Kotlin are considered *value objects*, they’re defined by their properties. So the way to make them unique is to give them a proper identity. By doing this, we will avoid falling into scenarios where many different Cells could be considered the same just because all of them are `Alive`

or `Dead`

, for example.

For simplicity, we will generate our ids using `UUID.randomUUID().toString()`

.

When it comes to modeling our `Universe`

, since it’s described as a grid of two dimensions where each position is considered a `Cell`

, we will use a simple `typealias`

.

```
typealias Universe = List<List<Cell>>
```

Given we’ve got direct interoperability between `List`

and Arrow’s `ListK`

(its Higher Kind counterpart), this is probably the most obvious way to model it.

Finally, since we will also need to reason about positions more than once, it seems convenient to model them as a class (they could also be simple tuples).

```
data class Position(val x: Int, val y: Int)
```

## Writing tests first

As explained in the beginning, by reading the problem description, we will find a clearly defined **program state** that gets generated multiple times **sequentially**, and, for each generation, it must satisfy a constrained set of rules:

- Any live cell with two or three neighbors survives.
- Any dead cell with three live neighbors becomes a live cell.
- Any live cell with fewer than two live neighbors dies, as if by underpopulation.
- Any live cell with more than three live neighbors dies, as if by overpopulation.

We’ve got four very well-defined properties that could become very straightforward tests we could write to ensure our program does what’s expected.

This looks like a perfect situation to benefit from writing tests first, then solving our problem. That’ll probably shortcut some problems beforehand. To write those, we’ll be using KotlinTest and **property based testing**. You can take a look to those here.

As a summary, we generate universes with dimension 3x3, given that’s the minimum `Universe`

we’d need to validate the required properties, since those are based on the state of the current `Cell`

and all its neighbors (surrounding ones). The `Universe`

generator looks like this:

```
class UniverseGen(private val center: Cell, private val aliveNeighbors: Int) : Gen<Universe> {
override fun constants(): Iterable<Universe> = emptyList()
override fun random(): Sequence<Universe> = generateSequence {
val alive = (1..aliveNeighbors).map { Cell.Alive() }.toList()
val dead = (1..(8 - aliveNeighbors)).map { Cell.Dead() }.toList()
val all = alive + dead
all.shuffled().toGrid(center)
}
private fun List<Cell>.toGrid(center: Cell): List<List<Cell>> =
listOf(
listOf(get(0), get(1), get(2)),
listOf(get(3), center, get(4)),
listOf(get(5), get(6), get(7))
)
}
fun universeGenWith2or3AliveNeighbours(cell: Cell) =
Gen.choose(2, 3).flatMap { UniverseGen(cell, it) }
fun universeGenFewerThan2AliveNeighbours(cell: Cell) =
Gen.choose(0, 1).flatMap { UniverseGen(cell, it) }
fun universeGenMoreThan3AliveNeighbours(cell: Cell) =
Gen.choose(4, 8).flatMap { UniverseGen(cell, it) }
```

We pass a `Cell`

to use as the center (`Position(1, 1)`

) and that we’ll use as the reference for our tests to assert over, then generate up to eight neighbors around it with a random state each (`Alive`

or `Dead`

).

We also provide some handy methods to shortcut some specific scenarios we’ll be interested in for testing our given properties.

For more details, again, please don’t hesitate to take a look at our tests.

## Our solution

Thinking back to the problem definition, we identify a `State`

that’s generated based on the previous `State`

of the program on each *tick*. That’s essentially the definition of the `State`

Monad, since it wraps a computation with the type `(S) -> Tuple2<S, A>`

, where `S`

is the input and output state, and `A`

is the potential result of the computation, if needed.

In this case, we’ll just be interested in the actual evolving state, so we can use `Unit`

for `A`

.

We can achieve sequential generations by using `flatMap`

, which is what it’s defined for. We have State in Arrow, so we could definitely go with it and encode our solution maybe like this:

```
fun gameOfLife(currentGeneration: Int = 0, maxGenerations: Int): State<Universe, Unit> =
State { universe: Universe ->
universe.tick()
}.flatMap(idMonad) {
if (currentGeneration < maxGenerations) {
gameOfLife(currentGeneration + 1, maxGenerations)
} else {
State.just(idMonad, it)
}
}
```

But we’ll also want to log the current state for each tick, so **we’ll have some side effects**, and `State`

is not defined to handle those. If we just logged within the `State`

invoke call along with the `tick()`

, the program could potentially blow up without any control.

Other types like `IO`

are defined to control effects. There’s actually a pretty interesting solution that just uses `IO`

by @pedrovgs. Take a look at it since it’s another valid approach.

In our case, we’ll use this chance to show a different alternative; not better, not worse, just different for academic purposes. We’ll be using `StateT`

, the **state transformer**.

`StateT`

is defined as `StateT<F, S, A>`

, so it can work over any `F`

. We’ll fix `F`

to be `IO`

here, since that will give us the chance to protect us against the side effects using the powers of `IO`

, but also to transform it, bringing the capabilities of `State`

to it so we can use them to model our evolving program state.

This is how our Game of Life solution looks:

```
fun gameOfLife(maxGenerations: GenerationCount = Infinite, currentGeneration: Int = 0): StateT<ForIO, Universe, Unit> =
StateT(IO.monad()) { universe: Universe ->
IO {
println(universe)
universe.tick()
}
}.flatMap(IO.monad()) {
when (maxGenerations) {
is Infinite -> gameOfLife(maxGenerations, currentGeneration + 1)
is Finite -> if (currentGeneration < maxGenerations.count - 1) {
gameOfLife(maxGenerations, currentGeneration + 1)
} else {
StateT.just(IO.monad(), it)
}
}
}
```

We log the universe, then tick (so we also log the initial state). Then we can `flatMap`

the program over itself so we get a potentially infinite recursion that’s **lazily evaluated** (one tick at a time) thanks to the inherent capabilities of `State`

(it wraps a computation that requires some state to run, hence it waits for it).

We also used the chance to improve the `maxGenerations`

a bit by using a sealed class that can be `Finite`

or `Infinite`

. The `Finite`

one will be very handy in tests since we’ll just need a few generations to ensure the program works and complies to the required laws.

Of course the `tick()`

function encodes all the program requirements, like:

```
private fun Universe.tick(): Tuple2<Universe, Unit> {
val newGeneration = this.map { column ->
column.map { cell ->
val aliveNeighbors = cell.aliveNeighbours(this).size
when {
aliveNeighbors < 2 || aliveNeighbors > 3 -> Cell.Dead()
aliveNeighbors == 3 && cell.isDead() -> Cell.Alive()
else -> Cell.Alive()
}
}.k()
}.k()
return newGeneration toT Unit
}
```

The rules are very self descriptive.

To get the neighbors of a cell, we use the powers of `ListK`

cartesian product to get the potential deltas, then `filterMap`

the ones that don’t have valid positions on the grid (e.g.: some positions around the edges).

```
fun Cell.neighbours(universe: Universe): List<Cell> {
val allDeltaCombinations = listOf(-1, 0, 1) * listOf(-1, 0, 1) // ListK cartesian product to get all combinations
val deltas = allDeltaCombinations - Tuple2(0, 0)
return deltas
.filterMap { universe.cellPosition(this).shiftBy(universe, it) }
.map { universe[it.x][it.y] }
}
```

We can use `filterMap`

because we return `Option`

from `cellPosition`

and `shiftBy`

, so non valid positions are returned as `None`

, hence filtered out. You can dig into the details in the source code.

## Running the program

Given that `State`

and `StateT`

require an initial state to run, we can pass it using the convenient `run`

function provided for it. Since our `StateT`

returns an `IO`

, we’ll also need to unsafely run it in this case.

```
fun main() {
gameOfLife(Finite(3)).run(IO.monad(), initialSeed()).fix().unsafeRunSync()
}
```

Here we are constraining the max number of generations to `3`

.

## Conclusions

You can take a look at the entire implementation at my Conway’s Game of Life repository.

We hope you enjoyed this exercise, and we look forward to seeing your takes on this challenge using Kotlin and Arrow. So please, share them with us!

Please check out the following Arrow resources. Comments and questions are welcome and encouraged!

- arrow-kt.io
- @arrow_kt on Twitter
- Arrow Gitter Channel
- My Twitter profile
- My blog where I post a lot about Functional Programming.

The active development of Arrow is proudly sponsored by 47 Degrees, a Functional Programming consultancy with a focus on the Scala, Kotlin, Haskell, and Swift Programming languages.