Type Class 101: Semigroup

Almost immediately when I started to program in Scala, I became intruiged by scalaz, the scala type class library. After playing and learning a bit, I decided that I essentially rewrite the library to get a better understanding of its concepts. I do not intend to replace scalaz, I skip lots of the optimization techniques, and left out many of the “non essential functions”. Gradually I will blog about the experiences and compile a tutorial much in the style of the essential Learning scalaz by Eugene Yokota.

What is a type class

wikipedia: A type class F describes a set of functionality for some type A which this type must adhere to, if we build an instance of F[A].This allows us to use ad hoc polymorphism and we avoid complex and brittle inheritance structures.

Semigroup

On of the most simple type classes around is the semigroup. It defines one operation, by convention called append which has the following signature

def append(a: A, b: A) : A

Or as a complete example:

trait Semigroup[A] {
  def append(a: A, b: A): A
}

Type class laws

Each type class usually comes along with some laws, which have to be obeyed by all instances of this typeclass. For a semigroup it is the law of associativity, which states that (simplified notation) append(a1, append(a2, a3) == append(append(a1, a2), a3). These laws must hold at all costs.

Implicit type class instances

Once we have defined our type class we can provide instances for it. One simple case of a semigroup instance is

implicit val intSemigroup = new Semigroup[Int] {
  def append(a: Int, b: Int) : Int = a + b
}

Here we have defined a semigroup for Int and addition, and we know that the law of associativity holds for natural numbers. We could (and can) also define

implicit val intSemigroup = new Semigroup[Int] {
  def append(a: Int, b: Int) : Int = a * b
}

and we again know that multiplicity obeys our law of associativity. In contrast

implicit val intSemigroup = new Semigroup[Int] {
  def append(a: Int, b: Int) : Int = a / b
}

is not a valid instance of a semigroup. We do not even have to consider the law of associativity, it is enough that this instance violates our contract to give us an Int for every Int a, b, which is not true for b==0. Sure enough - we could get away with just throwing an exception, but …

Type classes, type class instances and laws => Reasoning in patterns about code and algorithms

As we will construct more and more complex programms with the help of type classes, it is extremely important that we obey the laws. If we can rely on them, we can predict the behaviour of the code. No side effects, exceptions and obscure assumptions dampen our understanding of the code. We will also learn to think in patterns of behaviour and structure, much like when we use design patterns in (sic) java, only that our patterns are sound and safe (and beautiful).

Putting it all together with a nice syntax

When we want to use our new semigroup there are essentially two common patterns. I call the first one direct invocation, and it looks like this:

Semigroup[Int].append(1,2) == 13

We essentially call the apply function of a Semigroup object, which is defined like this:

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

This object looks for an implicit definition of a semigroup for our type A and returns it, so that the call above resolves to Semigroup.applyInt.append(1,2)

The second approach uses Syntax classes which help us to write code like this:

3.append(4) == 7

As Int obviously does not have an append method, we help with some implicit definitions:

trait SemigroupSyntax[A] {
  def self: A
  def F: Semigroup[A]
  def |+|(b: A): A = append(b) // alias for append
  def append(b: A): A = F.append(self, b)
}

implicit def ToSemigroupOps[A: Semigroup](a: A): SemigroupSyntax[A] =
  new SemigroupSyntax[A] {
    def self: A = a
    def F: Semigroup[A] = implicitly[Semigroup[A]]
}

This approach utilizes a trait in order to define the syntax for our semigroup as if we had already one parameter (self) at hand, and the implicit operation just provides us with an instance of this trait, by providing us our self and a matching instance of our typeclass in F.

Other instances of Semigroup

When we apply what we learned so far, it is easy to come up with more instances, e.g. for Long, Char, Boolean (acutally 2), … But what about an Option[A]? Well, we can define a semigroup for Option[A] if there is a semigroup for A:

implicit def optionInstances[A: Semigroup] = new Semigroup[Option[A]] {

  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(_), None) => a
      case (None, Some(_)) => b
      case _ => None
    }
  }
}

Further learning

I have learned a lot by writing my own small type class library and stole a lot of code from scalaz. You can checkout simplez here: SimpleZ and scalaz here: scalaz When you want to compare the code above to scalaz, you can see the slightly more complicated version here: Semigroup along with the instances here: Instances AnyVal and the syntax classes here: SemigroupSyntax. I even put an alias in my .profile to jump immediately to the scalaz code: alias scalaz="cd $PROJECTS/scala/scalaz/core/src/main/scala/scalaz"

Further articles will be published under the category typeclass101.

typeclass101 scalaz scala

Kommentare