The composite pattern and monoids

When you hear some one mention the Composite Pattern you might have visions race through your head of "The gang of four", enterprise development and old neck beard programmers. Likewise, when you hear some one mention Monoid, visions of Haskell, complicated FP development and hipsters may race through your head. Bringing such jarringly different first impressions, what can the Composite Pattern possibly have in common with Monoids?

To begin to explore a possible relationship we must first start at definitions.

The Composite Pattern

In software engineering, the composite pattern is a partitioning design pattern. The composite pattern describes that a group of objects are to be treated in the same way as a single instance of an object. The intent of a composite is to "compose" objects into tree structures to represent part-whole hierarchies. Implementing the composite pattern lets clients treat individual objects and compositions uniformly.  

You can effectively model this in Scala by having an abstract trait as an interface and applying that trait to both a singular representation of an object and to a plural collection of the same object. Using a Raven object as the singular and a RavenFlock object as the plural and having them both implement the abstract trait Bird we would lay this out in Scala as follows

sealed trait Bird {

  def fly(vector: MovementVector): Bird

  def eat(food: Food): Bird

}

case class Raven(position: Coordinates, belly: Stomach) extends Bird {

  def fly(vector: MovementVector): Bird = {
    this.copy(position = position.move(vector))
  }

  def eat(food: Food): Bird = {
    this.copy(belly = belly.consume(food))
  }

}

case class RavenFlock(birds: List[Raven]) extends Bird {

  def fly(vector: MovementVector): Bird = {
    birds.foldLeft(List()) { (birds, bird) =>
      birds :+ bird.fly(direction)
    }
  }

  def eat(food: Food): Bird = {
    birds.foldLeft(List()) { (birds, bird) =>
      birds :+ bird.eat(food)
    }
  }

}

This implementation allows us to control entire flocks of ravens through the same interface which we would use to control any singular raven. This is pretty useful and is the net effect of using the Composite Pattern.

Monoid

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for instance, they can be regarded as categories with a single object. Thus, they capture the idea of function composition within a set.  

So in essence, a Monoid is just an interface with one abstract value and one abstract method. The abstract method for a Monoid is the append operation. It's also refered to as mappend or simple aliased as the + operator. The abstract value for a Monoid is the identity value. The identity value is defined as the value you can append to any value that will always result in the original value unmodified. In terms of integers, 0 is the identity value because anything you add/append to it will produce the value you tried to append to it. In terms of collections the identity value is typically the empty collection because appending a collection to an empty collection will typically produce the same collection unmodified.

So we can model this out in Scala with Raven objects and RavenFlock objects by adding an append (+) method that takes Raven and RavenFlock objects, joins them together and produces a new flock of of both of them.

sealed trait Bird {

    def +(other: Bird): Bird

}

case class Raven(position: Coordinates, belly: Stomach) extends Bird {

  def +(other: Bird): Bird = other match {
    case Raven(p, b)   => RavenFlock(Raven(p, b)) + this
    case RavenFlock(b) => RavenFlock(b) + this
  }

}

case class RavenFlock(birds: List[Raven]) extends Bird {

  def +(other: Bird): Bird = other match {
    case Raven(p, b)   => this.copy(birds = birds :+ Raven(p, b))
    case RavenFlock(b) => this.copy(birds = birds + b)
  }

}

This allows us to take either a singular Raven or a plural RavenFlock, add them together and get back a composite of the two. The identity value in this case is an empty RavenFlock RavenFlock(List()).

Bringing it all together

An interesting observation i've made with the Composite Pattern and Monoids is almost every time you have one, theres almost always an opportunity for the other. Meaning every time you have a Monoid, you know you can almost always implement the Composite Pattern on the same type effectively for free and vice versa.

Bringing our implementations together in Scala would look like this

sealed trait Bird {

  def fly(vector: MovementVector): Bird

  def eat(food: Food): Bird

  def +(other: Bird): Bird

}

case class Raven(position: Coordinates, belly: Stomach) extends Bird {

  def fly(vector: MovementVector): Bird = {
    this.copy(position = position.move(vector))
  }

  def eat(food: Food): Bird = {
    this.copy(belly = belly.consume(food))
  }

  def +(other: Bird): Bird = other match {
    case Raven(p, b)   => RavenFlock(Raven(p, b)) + this
    case RavenFlock(b) => RavenFlock(b) + this
  }

}

case class RavenFlock(birds: List[Raven]) extends Bird {

  def fly(vector: MovementVector): Bird = {
    birds.foldLeft(List()) { (birds, bird) =>
      birds :+ bird.fly(direction)
    }
  }

  def eat(food: Food): Bird = {
    birds.foldLeft(List()) { (birds, bird) =>
      birds :+ bird.eat(food)
    }
  }

  def +(other: Bird): Bird = other match {
    case Raven(p, b)   => this.copy(birds = birds :+ Raven(p, b))
    case RavenFlock(b) => this.copy(birds = birds + b)
  }

}

Now our Bird objects are both Monoids and implementations of the Composite Pattern. We can join various combinations of them together to produce aggregate versions and we can operate on the plurals through the same interface we would the singulars.

Other

This seems slightly wrong though. Should we ever allow a developer in our system to create, use or have an empty RavenFlock? It seems like an illegal state that should be made unrepresentable. Luckily for us, we can easily make the state of emptiness illegal by using Semigroups instead of Monoids, i'll leave this as an exercise for the reader for now in the name of not derailing the intent of this post. In cases where it is viable to have empty collections floating around your system Monoid is more then suitable.