Skip to content

Instantly share code, notes, and snippets.

Last active Jan 5, 2018
What would you like to do?
Basic write-up of how Cats supports using symbolic operators with type classes.

Symbolic operators and type classes for Cats

One of the simplest and most recognizable type classes is the semigroup. This type class abstracts over the ability to combine values of a certain type in an associative manner.

Cats provides cats.Semigroup[A] to model semigroups [1]. The combine method takes two values of the type A and returns an A value.

In addition, Cats defines syntax allowing the binary operator |+| to be used in place of the combine method.

Small example

Here is a small method that provides a generic way to combine the elements of a list:

import cats.Semigroup
import cats.implicits._

def gsum[A: Semigroup](values: List[A]): Option[A] =
  if (values.isEmpty) None else values.reduceLeft((x, y) => x |+| y)

(A similar method is built into Cats as Semigroup.combineAllOption.)

How does it work?

One of the parts of gsum that might be hard to understand is where the |+| method comes from. Since x and y are totally generic values (of type A) how can we call a method on them?

To boil the example down further, consider this simpler example:

import cats.implicits._
19 |+| 20 // produces 39

How does this work? We know that the Int type does not have a |+| method. Experienced Scala developers will suspect that implicits play a role here, but what are the details?

In detail

Let's walk through how the expression 19 |+| 20 is compiled.

First, a |+| method is needed on Int. Since Int does not provide one, the compiler searches for an implicit conversion to a type that does have a |+| method.

Due to our import, it will find the semigroupSyntax[A] method, which returns a type that has a |+| method (specifically SemigroupOps[A]). However, semigroupSyntax requires an implicit Semigroup[A] value to be in scope. Do we have a Semigroup[Int] in scope?

Yes we do. Our import also provides an implicit value intGroup of type AdditiveCommutativeGroup[Int]. Leaving aside what additive, commutative, and group mean here, this is a subtype of Semigroup[Int], so it matches.

Let's continue with our current example. At this point we have gone form:

19 |+| 20 // produces 39


semigroupSyntax[Int](19)(intGroup) |+| 20

But we aren't out of the woods yet! We still need to see how this expression is evaluated.

Of macros and machinists

Looking at how the |+| method is implemented reveals the cryptic macro Ops.binop[A, A]. What is this?

Following the rabbit hole farther, we come to cats.macros.Ops which provides the macro implementation that |+| is using. Aside from a suggestively named item in the operatorNames map, we don't have any clues what is going on.

The machinist project was created to optimize exactly this kind of implicit syntax problem. What will happen here is that operatorNames describes how to rewrite expressions using type classes. Long-story short, we will transform:

semigroupSyntax[Int](19)(intGroup) |+| 20


intGroup.combine(19, 20)

The suggestive map item tells us that we should rewrite the |+| operator to method calls on the given type class (i.e. intGroup) using .combine.

Finishing up

Just to confirm that we're done, let's look at what intGroup.combine will do. We started with a call to AdditiveCommutativeGroup[Int], which will find intAlgebra. Then we call the .additive method on it to produce a CommutativeGroup[Int].

So putting that together, we can see that calling intGroup.combine(19, 20) will call, 20), and that this is defined as 19 + 20, as we would expect.



This is a lot of machinery. The incredibly terse and expressive syntax it enables is quite nice, but you can see that even leaving out one import will cause the whole edifice to come tumbling down.

The easiest way to use Cats is to just import cats.implicits._. That way, you can be sure that you have all of it. There are individual imports from cats.syntax and cats.std which can be used to pinpoint the exact values and method you want to put into scope, but getting these right can be a bit tricky, especially for newcomers.


You may also decide that the syntax convenience is not worth it. To write our original example without syntax implicits (but still using implicit values) you could say:

import cats.Semigroup
import cats.implicits._

def gsum[A](values: List[A])(implicit s: Semigroup[A]): Option[A] =
  if (values.isEmpty) None else values.reduceLeft((x, y) => s.combine(x, y))

// values.reduceLeft(s.combine) would also work

Whether to use syntax implicits or explicit method calls is mostly a matter of preference. Personally, I like using syntax explicits to help make generic code read in a clearer manner, but as always, your mileage may vary.


[0] Links accurate as of commit 82dbf4076572dfbb6e29dd49875f5e5d929f80be.

[1] cats.Semigroup is actually an alias to algebra.Semigroup. Algebra was created to share algebraic type classes between Spire, Algebird, Cats, and other projects.

[2] For more information about how Machinist works, see this example from Machinist's README as well as this gist contrasting Machinist's approach with value classes.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment