Adam Gajek
18 Mar 2019
•
6 min read
In this blog post you will learn about how to implement your first type class, which is fundamental language feature in the icon of the functional programming languages — Haskell.
Type Class is a pattern that originates from Haskell and it is its standard way of implementing polymorphism. This type of polymorphism is called ad-hoc polymorphism. Its name comes from the fact that contrary to well-known sub typing polymorphism we can extend some functionality of library even without having access to source code of library and class which functionality we want to extend to.
In this post you will see that using type classes can be as convenient as using regular OOP polymorphism. Content below will lead you through all phases of implementation of Type Class pattern to help you gain better understanding about internals of functional programming libraries.
Technically Type Class is just a parameterized trait
with number of abstract methods that can be implemented in classes that extend that trait. As far everything looks really like in well-known sub-typing model.
The only difference is that with help of sub-typing we need to implement contract in classes that are a piece of domain model, in Type Classes implementation of trait are placed in completely different class which is linked to “domain class” by type parameter.
As an example in this article I’ll use the Eq Type Class from Cats library.
trait Eq[A] {
def areEquals(a: A, b: A): Boolean
}
Type Class Eq[A]
is a contract of having an ability to check if two objects of type A are equal based on some criteria implemented in areEquals
method.
Creating instance of our Type Class is as simple as instantiating class that extends mentioned trait
with only one difference that our type class instance will be accessible as implicit object.
def moduloEq(divisor: Int): Eq[Int] = new Eq[Int] {
override def areEquals(a: Int, b: Int) = a % divisor == b % divisor
}
implicit val modulo5Eq: Eq[Int] = moduloEq(5)
Above piece of code can be compacted a little bit in a following form.
def moduloEq: Eq[Int] = (a: Int, b: Int) => a % 5 == b % 5
But wait, how can you assign function (Int, Int) => Boolean
to reference with type Eq[Int]
?! This thing is possible thanks to Java 8 feature called Single Abstract Method type of interface. We can do such a thing when we have only one abstract method in our trait
.
In this paragraph I’ll show you how to use type class instances and how to magically bind together type class Eq[A]
with corresponding object of type A
when it will be necessary.
Here we’ve implemented functionality of comparing two Int
values by checking if their modulo division values are equal. With all that job done we are able to use our Type Class for performing some business logic e.g. we want to pair two values that are modulo equal.
def pairEquals[A](a: A, b: A)(implicit eq: Eq[A]): Option[(A,A)] = {
if(eq.areEquals(a,b)) Some((a,b)) else None
}
We’ve parameterized function pairEquals
to be working with any types providing instance of class Eq[A]
available in its implicit scope.
When compiler won’t find any instance that matches to the above declaration it will end up with compilation error warning about lack of proper instance in provided implicit scope.
A
.eq: Eq[A]
with keyword implicit will trigger suggestion to look for object of type Eq[A]
in implicit scope.Thanks to implicits and typed parameters, compiler is able to bind together class with its corresponding type class instance.
All instances and functions are defined, let’s check if our code gives valid results
pairEquals(2,7)
res0: Option[(Int, Int)] = Some((2,7))
pairEquals(2,3)
res0: Option[(Int, Int)] = None
As you see we received expected results so our type class is performing well. But this one looks a little bit cluttered, with fair amount of boilerplate. Thanks to magic of Scala’s syntax we can make a lot boilerplate disappear.
The first thing I want to improve in our code is to get rid of second argument list (that with implicit keyword). We are not passing directly that one when invoking function, so let implicit be implicit again. In Scala implicit arguments with type parameters can be replaced by language construction called Context Bound.
Context Bound is declaration in type parameters list which syntax A : Eq
says that every type used as argument of pairEquals
function must have implicit value of type Eq[A]
in the implicit scope.
def pairEquals[A: Eq](a: A, b: A): Option[(A, A)] = {
if(implicitly[Eq[A]].areEquals(a,b)) Some((a,b)) else None
}
As you’ve noticed we ended up with no reference pointing to implicit value. To overcome this problem we are using function implicitly[F[_]]
which pulls found implicit value by specifying which type we refer to.
This is what Scala language offers us to make it all more concise. It still doesn’t look good enough for me though. Context Bound is a really cool syntactic sugar, but this implicitly seems to pollute our code. I’ll make a nice trick how to overcome this problem and decrease our implementation verbosity.
What we can do is to provide parameterized apply function in companion object of our type class.
object Eq {
def apply[A](implicit eq: Eq[A]): Eq[A] = eq
}
This really simple thing allows us to get rid of implicitly and pull our instance from limbo to be used in domain logic without boilerplate.
def pairEquals[A: Eq](a: A, b: A): Option[(A, A)] = {
if(Eq[A].areEquals(a, b)) Some((a, b)) else None
}
The next thing I want to get onto my workbench is Eq[A].areEquals(a,b
). This syntax looks very verbose because we explicitly refer to type class instance which should be implicit, right? Second thing is that here our type class instance acts like Service (in DDD meaning) instead of real A
class extension. Fortunately that one also can be fixed with help of another useful use of implicit
keyword.
What we will be doing here is providing so called syntax
or (ops
like in some FP libraries) module by using implicit conversions which allows us to extend API of some class without modifying its source code
implicit class EqSyntax[A: Eq](a: A) {
def ===(b: A): Boolean = Eq[A].areEquals(a, b)
}
This code tells compiler to convert class A
having instance of type class Eq[A]
to class EqSyntax
which has one function ===
. All this things make an impression that we’ve added function ===
to class A without source code modification.
We’ve not only hidden type class instance reference but also provide more class’y syntax which makes impression of method ===
being implemented in class A
even we do not know anything about this class. Two birds killed with one stone.
Now we are allowed to apply method ===
to type A whenever we have EqSyntax
class in scope. Now our implementation of pairEquals will change a little bit, and will be as follows.
def pairEquals[A: Eq](a: A, b: A): Option[(A, A)] = {
if(a === b) Some((a, b)) else None
}
As I promised we’ve ended up with implementation where the only visible difference comparing to OOP implementation is Context Bound annotation after A
type parameter. All technical aspects of type class are separated from our domain logic. That means you can achieve way more cool stuff (which I will mention in the separate article what will be published soon) without hurting your code.
As you see type classes in Scala are strictly dependant on using implicit feature so it is essential to understand how to work with implicit scope.
Implicit scope is a scope in which compiler will search for implicit instances. There are many choices so there was a need to define an order in which instances are looked for. The order is as follows:
It is so important because when compiler finds several instances or not instances at all, it will raise an error. For me the most convenient way of getting instances of type classes is to place them in the companion object of type class itself. Thanks to that we don’t need to bother ourselves with importing or implementing in-place instances which allows us to forget about location issues. Everything is magically provided by the compiler.
So lets discuss point 3 using example of well-known function from Scala’s standard library sorted
which functionality is based on implicitly provided comparators.
sorted[B >: A](implicit ord: math.Ordering[B]): List[A]
Type class instance will be searched in:
Those all things help a lot when using type class pattern but these is repeatable work that must be done in every project. These clues are an obvious sign that process can be extracted to library. There is an excellent macro-based library called Simulacrum, which handles all stuff needed for generating syntax
module (called ops
in Simulacrum) etc. by hand.
The only change we should introduce is the @typeclass
annotation which is the mark for macros to expand our syntax module.
import simulacrum._
@typeclass trait Eq[A] {
@op(“===”) def areEquals(a: A, b: A): Boolean
}
The other parts of our implementation don’t require any changes. That’s all. Now you know how to implement type class pattern in Scala by your own and I hope you gained awareness into how libraries as Simulacrum works.
Thanks for reading, I’ll really appreciate any feedback from you and I’m looking forward meeting with you in future with another published article.
Adam Gajek
See other articles by Adam
Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ
108 E 16th Street, New York, NY 10003
Join over 111,000 others and get access to exclusive content, job opportunities and more!