Refactoring with Monoids and Sum Types — Part 2

In the previous part we introduced monoids and refactored a simple game inventory to understand item management as addition of inventory slots.

Our set based solution had some drawbacks, however, most of all an over-reliance on Set, which is a platform type. While Kotlin has extension methods to enrich types with functionality, it would be ill advised to let your domain model spill into external modules. Moreover, relying on a single type to represent all required cases means that our model isn’t represented fully in the type system, which means we cannot lean on the compiler to verify correctness or leverage useful properties of object-functional languages such as subtype polymorphism. With this in mind, let’s see how we can pour our model into a custom type.

Let’s recap quickly what we want:

• Our item type should explicitly encode our model, which is to have three distinct cases: no item, one item, or a stack of items.
• We would like it to maintain its monoidal properties, plus commutativity.

We’ll look at the first problem first. Whenever you need “distinct cases”, chance are you want a sum type, given you’re fortunate enough to work with a programming language allowing you to express this. Sum types are algebraic data types that represent mutually exclusive cases. Hence the term sum: they represent the disjoint union of their value sets, which is sometimes denoted as + (not to be confused with the addition operator we introduced earlier!)

Here’s one way to declare our inventory element type:

sealed class Elem {
  abstract operator fun plus(el: Elem): Elem
}

What we’re saying here is that there exist a set of objects that we can combine using the + operator. We furthermore indicate this to be a sealed hierarchy, meaning all cases will be known to the compiler upfront. I’ll discuss the significance of this in a minute. Let’s define our cases now, starting with the simplest one (the empty element), working our way up to stacks. Here’s the empty case:

object Empty : Elem() {
  override fun plus(e: Elem): Elem = e
}

Pretty straight forward. We’re applying the null-object pattern here to represent our neutral element: a singleton object that leaves its input untouched. This makes it efficient and safe, without having to rely on nulls and the typically defensive code accompanying it.

Our single item case is a bit more interesting:

data class Item(val obj: GameObject) : Elem() {
  override fun plus(el: Elem): Elem =
      when (el) {
        is Empty -> this
        is Item -> ItemStack(setOf(this, el))
        is ItemStack -> ItemStack(el.items + this)
      }
}

This is slightly more complicated, but still quite intuitive: adding nothing simply yields the item back, adding another item creates a new stack, and adding a stack grows the stack with the item. You can see Kotlin’s smart casts at work here: matching a type via is allows us to refer to the object as that type in the lexical scope that follows.

Finally, adding stacks:

data class ItemStack(val items: Set<Item>) : Elem() {
  init {
    require(items.size > 1) { "Stacks must contain > 1 items" }
  }
  override fun plus(e: Elem): Elem =
      when (el) {
        is Empty -> this
        is Item -> ItemStack(this.items + el)
        is ItemStack -> ItemStack(this.items + el.items)
      }
}

We’re making generous use of the Set::plus operator here, which we can use to merge stacks, but note how this is merely an implementation detail. We also added a check ensuring that stacks must never contain fewer than two items. Since stacks can currently only grow larger, not shrink, this is sufficient to enforce the > 1 items invariant.

We’re now ready to combine inventory items freely, without having to worry about whether they’re empty, single items, or stacks. We can furthermore exploit sub-type polymorphism to dynamically dispatch to the correct + implementation based on the case type. Here’s a few examples:

val item1 = Item(sword1)
val item2 = Item(sword2)
val stack = item1 + item2 // creates an ItemStack
val stillItem1 = Empty + item1 // this compiles and works!
...

Our move function remain almost unchanged (that’s a good sign!), except for a change in the element type:

fun move(inventory: Array<Elem>, from: Int, to: Int) {
  inventory[to]   = inventory[to] + inventory[from]
  inventory[from] = Empty
}

Needless to say, we had to bring back some complexity that we had gotten rid of earlier when using just sets. This seems to be a small price to pay, however, considering that we now own the model implementation and can extend it as needed.

Before we move on, I promised I’d get back to the sealed keyword and its significance with respect to sum types. Since sum types represent disjoint unions of cases, we’re usually interested in whether a particular when clause handles all possible cases. If we accidentally forgot to handle a particular case when we need to return a value, the only possible option for the program would be to crash, because how would it know what to return?

This is where sealed comes in. Since a sealed hierarchy is impossible to extend with new cases outside its lexical scope, the compiler knows exactly when a particular when clause is exhaustive; if it’s not, we can fail compilation and thus prevent our program from crashing at runtime. This is something we wouldn’t be able to do with sets: because our cases were not explicitly encoded in the type system, but were just reflections of set contents (i.e. dynamic data), the compiler would never know if we were handling all cases properly.

Before wrapping up, let’s see what we got in terms of extra flexibility by defining a new type. After all, this was one of the primary reasons for not relying on sets. Considering that we’d want to render our inventory elements at some point, it would be useful to have a function yielding the first item in a slot, so that we can use its sprite to render the slot contents. This is convenient when dealing with stacks, since we can simply represent them by the first element they contain (we’re assuming they’re all of the same kind.)

Here’s how we could extend our Elem type to define yieldFirst as a higher-order function:

sealed class Elem {
  abstract operator fun plus(e: Elem): Elem

  inline fun yieldFirst(f: (Item) -> Unit) =
      when (this) {
        is Empty -> Unit
        is Item -> f(this)
        is ItemStack -> f(this.items.first())
      }
}

We could have also made the function abstract and have the sub-types implement it accordingly, but it was a bit more compact to do it in Elem itself. Again, the compiler forces us to deal with all possible cases, and it’s safe to even call it on empty slots, in which case it will be a no-op:

Empty.yieldFirst(::renderItem) // does nothing
Item(obj1).yieldFirst(::renderItem) // renders a sword
(Item(obj1) + Item(obj2)).yieldFirst(::renderItem) // render stack

Or we could simply do it as a batch operation:

fun renderAll() = inventory.forEach { it.yieldFirst(::renderItem) }

Kotlin will desugar these calls to efficient loops when compiling this down to Java byte code.

I hope I could demonstrate how sometimes innocent looking problems can quickly lead to unwieldy, unsafe implementations. Applying even the simplest patterns such as a combination operator in a principled way can not only lead to a cleaner, more intuitive, and ultimately safer implementation, but might even make new functionality available for free that you had not initially thought about, be it generic algorithms like folds or simply getting better feedback from the compiler.