In July 2020 I gave a presentation at the functional programming guild for my employer REA Group. The talk involved slowly building a type class hierarchy extending from semigroup. Each additional step added the laws required by the child type class.
The semigroup hierarchy visualisation
I wrote a small project called laws-playground which uses graphviz with d3
to produce this graph. You can explore how different type/operation combinations comply with the type classes we
explored with the drop down.
As part of the presentation, we defined a graph of type classes, and then instances for a number of types and binary
operations. For example, the magma-semigroup-monoid relationship and an instance for Int would look like:
val magma = TypeClass(
name = "Magma",
parents = Set.empty,
laws = Set(
Laws.binaryOperation,
)
)
val semigroup = TypeClass(
name = "Semigroup",
parents = Set(magma),
laws = Set(
Laws.associativity,
),
)
val monoid = TypeClass(
name = "Monoid",
parents = Set(semigroup),
laws = Set(
Laws.identity,
),
)
val intUnderAddition = Instance[Int](
name = "Int under addition",
binaryOp = (i1: Int, i2: Int) => i1 + i2,
identity = 0,
)
Thoughts on the presentation
Mostly I’m putting this post up just to have somewhere to host the final graph. But I made a couple of decisions in the presentation that are worth reflecting on.
Focus on the visualisation. Downplay the Scala.
The code for this presentation makes use of a custom Scala DSL so that we could define laws while live coding. The end
result is visible in the Laws.scala
file in the repo.
Scala’s implicits can be used to create beautiful and totally inscrutable DSLs. Generally I think this is a flaw that makes the language appear “magic” to all but the most experienced Scala developers. In this case, though, I used these language features to build a DSL for the presentation. I then asked the audience to focus on the mathematical expressions and not worry about how it compiles in Scala. For example, my expression of associativity looks like:
val associativity: Law = new Law.With3Params(name = "associativity") {
override def test[A: Instance](a1: A, a2: A, a3: A): IsEq[A] =
((a1 + a2) + a3) alwaysEquals (a1 + (a2 + a3)) // 👈 Focus on this bit
}
Most of the code here doesn’t add much to the presentation, and some of it requires a strong understanding of implicits
to make much sense of. In particular, the + infix operator and the alwaysEquals method would require hours to
explain to a Scala neophyte. Instead, I asked those listening to my presentation to just focus on how they understood addition,
and reassured them that the key bit to focus on is the mathematical expression.
Once I got people comfortable with the focus on the expressions rather than the Scala, I made sure we focussed on how the above chart changed as we added type classes and their attendant laws. This meant we could keep the talk visual and accessible while live coding, even while de-emphasising the Scala we were writing.
Don’t even mention property-based testing
Testing laws in Scala is fundamentally linked to property-based testing (PBT). In this presentation I didn’t even
mention PBT. The code for laws-playground was designed specifically to hide it completely from the audience, apart
from a couple of imports at the top of our main file.
PBT is a fascinating concept, but explaining it would have detracted from our focus on laws as mathematical expressions and type classes. By doing enough work in the project background, I was able to hide this more advanced concept and keep the focus where I wanted it.
Using the magma type class to emphasise associativity
The inspiration for the graph was the semigroup hierarchy that comes with the cats functional programming library, which sees a lot of use in REA. The main addition I made was the magma type class at the root of the hierarchy. I found this concept by browsing Wikipedia (see article), so it’s definitely not something I have a deep understanding of!
The idea was to introduce some type class that was satisfied by simply having a binary operation. We can then add the
“associativity” law and discuss how it adds an additional constraint that gives us the semigroup type class. I used
“String under interleave” as an example of a type/operation combination that is a magma, but not a semigroup:
("abc" interleave "123" = "a1b2c3"
("abc" interleave "123") interleave "xyz" = "ax1ybz"
"abc" interleave ("123" interleave "xyz") = "a1bxc2"
This allowed us to emphasise that even this most trivial of laws (eg associativity) does exclude some operations that are easy to explain to an audience.
Side-point: magmas have to be closed
It’s worth pointing out that the requirement on magma in algebra is that it is closed
under the binary operation. For example, addition on the set {1, 2} is not closed, because 2 + 2 = 4 and 4 is not
part of the set.
I didn’t mention this in the presentation and it didn’t come up in questions. There’s a potentially interesting
conversation about the extent to which it is even possible to define an operation that isn’t closed in a strongly typed
language like Scala. A hacked-together type like IntBetween1And2 might allow you to demonstrate this as a law, but the
complexities in implementing it would probably detract from the more interesting lessons I was hoping to discuss in this
presentation.
Ask listeners to suggest their own instances
Having done the hard work in laws-playground, it was relatively easy to add new type/operation combinations to the
graph. We could easily establish which type classes these would honour. In the event, I added instances for Double to
check whether floating-point errors might mean it wasn’t a lawful field.
I had a question from the audience about how RGB colours would comply with the laws provided. I decided I probably couldn’t do this live, but it was an interesting question! Turns out, mixing colours is quite a complex topic, but I still think it would be interesting to investigate whether you can define a lawful group for colours.
The key point here is that if you do the work upfront, you can ask for contributions and suggestions from the audience while live coding. This keeps people engaged and makes them feel more comfortable asking questions.
Laws are interesting but not really useful
In the end, my thesis in this presentation was that laws and the type classes beyond monoid aren’t really that useful
for Scala developers. I’ve spent a bit of time thinking about how to define group or lattice instances for types like
java.time.Period (see post) or DupelessSeq,
but I haven’t been able to think of a time where these add much to the utility we get from having a cats.kernel.Monoid
instance defined.
I asked the audience to disagree with me, but nobody did. I’m happy to be convinced otherwise, but mostly I think this was an interesting but ultimately useless presentation.