Type Class 101: Monoid

In the last installment of this series, we had a look at one of the most primitive type classes, the semigroup. Today we add one nifty feature to it, namely the notion of an identity element zero:

trait Monoid[A] extends Semigroup {
  def zero : A
}

and again we supply a nifty object to get hold of the implicit instance in a unified way, like we did when we introduced the semigroup:

object Monoid {
  def apply[A](implicit F : Monoid[A]) : Monoid[A] = F
}

Of course there are again laws to obey, this time the identity laws, which state

  • zero append a == a
  • a append zero == a.

We can now extend our type class instances for numbers to use 0 as the identity element (under addition) or 1 (under multiplication). What is the zero for an Option[A] - well it is None:

// I give you an instance of a Monoid[Option[A]], if you give me a Semigroup[A]
implicit def optionInstance[A](implicit A: Semigroup) =
  new Monoid[Option[A]] {
    def zero : Option[A] = None
    def append(a : Option[A], b: Option[A]) : Option[A] =
      (a, b) match {
        case (Some(a1), Some(b1)) => Some(Semigroup[A].append(a1, b1))
        case (Some(_), _) => a
        case (_, Some(_)) => b
        case _ => zero
      }
  }

The code above is not so interesting in itself, but it introduces a nice pattern which is employed all over the place when programming with type classes. In order to compose your implementation (aka your type class instances) you make statements on constraints and thus also about assertions. Above we said, that we can provide anyone with an instance of a monoid for Option[A] as long as we can be sure that there is at least a semigroup available for A.

This constraint is not always required. If we consider for example how a monoid (and hence semigroup for a list would look like):

implicit def listInstance[A] = new Monoid[List[A]] {
   def zero : List[A] = List.empty[A]
   def append(a: List[A], b: List[A]) = a ++ b
}

we notice that we do not care about the inside of a list. We obey all the laws, and that’s it. And it is also worthwhile to accept that we rarely need to know something about the implemention of a given instance of a type class (which is a bit different when we look at the two implementions). It obeys the laws and that’s it (on the other hand, there is also nothing more satisfying in sniffing around some code to see how it works). If we focus for one second again on the implementation of the optionInstance, there is another pattern at work - we saw that we can prohibit the instantiation of the type class instance when we are not given a Semigroup[A], but what we can’t do, is change any of the function signatures, e.g. we can’t write something like

    def append(a: Option[A], b: Option[A])(implicit F : Semigroup[A]) = ...

because that would

  • not compile as we violate the contract of the trait Monoid
  • and we would violate our contract of the Monoid itself, leaving intricacies of the scala language aside.

Practical example

If we were to write a function to sum up elements of a List (example used from Nick Partridge)

implicit class SumOps(list : List[Int]) {
  def suml() : Int = list.foldLeft(0)(_ + _)
}

List(1,2,3).suml()                              //> res0: Int = 6

we could abstract this implementation and replace the type Int with any type for which we have a monoid instance:

implicit class SumOps2[A : Monoid](list : List[A]) {
  val F = implicitly[Monoid[A]]
  def suml() : A = list.foldLeft(F.zero)(F.append(_,_))
}

implicit val boolMonoid = new Monoid[Boolean] {
  def zero = true
  def append(a: Boolean, b: Boolean) : Boolean = a && b
}

List(true, false, true).suml()                  //> res0: Boolean = false

Ok - kind of boring - but what if we also have our option monoid instance in scope, which we defined above:

List(Some(true), Some(false), None, Some(true)).suml() //> res0: Option[Boolean] = Some(false)

Experiment a bit by taking implicit type class instance into and out of scope, to observe the compiler error messages. It helps to get a feel when thinks turn sour. List().suml() does not compile - investigate why.

Further learning

I recommend that you have a look again at the scalaz code for Monoid. It contains some other functions, for example multiply. Have a look and study these.

A man enters a bar, and sees Monoid.

He says: “Hello Monoid!”

Semigroup turns around and says: “I am not Monoid.”

The man: “Sorry, clear case of mistaken identity”

Don’t tell this at a party. Believe me, I tried. But I find it funny nevertheless. Actually I keep postponing posting this blog, because I laugh so much. I also cannot recommend enough to rebuild these examples. You may find that you have to write a lot of code in order to do a simple thing as summing up some values. But in order to build a house, you need nails, screws, wood and tools. Luckily the people at scalaz already build a complete Home Depot of useful tools for us. Only the aisles of the super market might look intimidating at first. By building your own corner shop, you get a feel for how they tick and where and how to look for information.

For further articles in this series: TypeClass101

typeclass101 scalaz scala

Kommentare