47 Degrees joins forces with Xebia read more

Conway's Game of Life using Kotlin and Arrow

Conway's Game of Life using Kotlin and 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, Haskell, and Scala.

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!

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

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.