[Check my articles on my blog here]

I will try to group here, in an anatomy atlas, basic notions of functional programming that I find myself explaining often lately into a series of articles.

The idea here is to have a place to point people needing explanations and to increase my own understanding of these subjects by trying to explain them the best I can.
I'll try to focus more on making the reader feel an intuition, a feeling about the concepts rather than on the perfect, strict correctness of my explanations.

Part 1: Anatomy of functional programming
Part 2: Anatomy of an algebra
Part 3: Anatomy of a type class
Part 4: Anatomy of semi groups and monoids
Part 5: Anatomy of functors and category theory
Part 6: Anatomy of the tagless final encoding - Yet to come !

Motivation

Data / behavior relationship

OOP and FP have two different approaches when it comes to data/behavior relationship:

Object oriented programming often combines data and behavior by mixing them into classes that:
- Store data as an internal state
- Expose methods that act on it and may mutate it
Functional programming aims to completely separate data from behavior by:
- Defining types (ADT on one side that expose no behavior and only holds data
- Functions taking values of some of these types as inputs, acting on them and outputting values of some of those types (leaving the input values unchanged)

You can check Anatomy of functional programming for examples.

Polymorphism

The general idea of polymorphism is to increase code re-use by using a more generic code.

The are several kinds of polymorphisms but the one adressed by type classes is ad hoc polymorphism, so we are going to focus on that one.

Ad hoc polymorphism is defined on Wikipedia by:

Ad hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types, because a polymorphic function can denote a number of distinct and potentially heterogeneous implementations depending on the type of argument(s) to which it is applied

It is a mechanism allowing a function to be defined in such a way that the actual function behavior that is going to depends on the types of the parameters over which it is applied to.

To make it clearer, Ad hoc polymorphism avoids you from having to define printInt, printDouble, printString functions, a print function is enough.

Our print will rely on ad hoc polymorphism to behave differently based on the type of the the parameter they are applied to.

The purpose of that is mainly to program by manipulating interfaces (as a concept, the layer allowing elements to communicate, not as in a Java Interface even their purpose is to encode that concept) exposing shared, common, behaviors or properties and use these behaviors instead of writing different function implementations for each of the concrete types abstracted by these interfaces.

Your print function might somehow require a Printable interface, abstracting for its argument the ability to print themselves.

Object oriented programming often use interface subtyping to permit polymorphism by making concrete classes inherit interfaces exposing the needed shared behaviors
Functionnal programming, willing to strongly separate data and behavior favours type classes which allows to add behaviors to existing types without having to modify them or having to plan they will need these functionnalities beforehand.

What's a type class ?

A type class can be described literally as a class of types, a grouping of types, that shares common capabilities.

It represents an abstraction of something that a grouping of types would have in common, just as "Things that can say Hi" abstracts over every concrete types that have the ability to greet or as "Things that have petals" might abstract over flowers in the real world.

It plays the same role as an interface in OOP but it is more than that:

It allows to add behavior to existing types (even type that are out of our codebase scope)
It permits conditionnal interfacing, by that I mean, we can encode that A is a member of the type class T1 if A is also a member of type class T2

How can it be done in Scala ?

Type classes are not specific to Scala and can be found in many functional programming languages.
They are not a first class construct in Scala, as it can be in Haskell but it still can be done quit easily.

In Scala it is encoded by:

A trait which exposes the "contract" of the type class, what the type class is going to abstract over,
The concrete implementations of that trait for every types that we want to be instances of that type classes.

Our type class for "types that can say Hi" is going to be:

trait CanGreet[T] {
    def sayHi(t: T): String
}

Representing all the types T which have the capability to sayHi.

Given a:

case class Player(nickname: String, level: Int)
val geekocephale = Player("Geekocephale", 42)

We now create a Player instance of the CanGreet trait for it to be an instance of our type class.

val playerGreeter: CanGreet[Player] = new CanGreet[Player] {
    def sayHi(t: Player): String = s"Hi, I'm player ${t.nickname}, I'm lvl ${t.level} !"
}

Thanks to what we did, we can now define generic functions such as:

def greet[T](t: T, greeter: CanGreet[T]): String = greeter.sayHi(t)

greet is polymorphic in the sense that it will work on any T as long as it gets an instance of CanGreet for that type.

greet(geekocephale, playerGreeter)

However, that is a bit cumbersome to use, and we can leverage Scala's implicits power to make our life easier (and to get closer to what's done in other languages' type class machinery).

Let's redifine our greet function, and make our CanGreet instance implicit as well.

Some hygiene guidelines comming from Haskell type classes:

Make your type class instances live
- Either in the type class companion object
- Or in the type's companion object of your type T, here Player
Have no more than one instance per type for a given type class (especially true in Scala)

Type class and type companion objects are nice places for type class instances because both of their scopes are checked when a function requires an implicit of type TC[T] where TC is your type class trait and T is the type for which you look for a type class instance.

object Player {
    implicit val playerGreeter: CanGreet[Player] = new CanGreet[Player] {
        def sayHi(t: Player): String = s"Hi, I'm player ${t.nickname}, I'm lvl ${t.level} !"
    }
}

def greet[T](t: T)(implicit greeter: CanGreet[T]): String = greeter.sayHi(t)

Now, we can call our greet function without explicitly passing the CanGreet instance as long as we have an implicit instance for the type T we are using in scope (which we have, playerGreeter) !

greet(geekocephale)

To sum up, here's all the code that we wrote so far:

trait CanGreet[T] {
    def sayHi(t: T): String
}

case class Player(nickname: String, level: Int)

object Player {
    implicit val playerGreeter: CanGreet[Player] = new CanGreet[Player] {
        def sayHi(t: Player): String = s"Hi, I'm player ${t.nickname}, I'm lvl ${t.level} !"
    }
}

def greet[T](t: T)(implicit greeter: CanGreet[T]): String = greeter.sayHi(t)

Optionnal cosmetics

That part is absolutely not mandatory to understand how type classes work, it is just about common syntax additions to what we saw before, mostly for convenience, and it can be skipped to go directly to conclusion.

def greet[T](t: T)(implicit greeter: CanGreet[T]): String

Is strictly the same thing and can be refactored as:

def greet[T: CanGreet](t: T): String

The function signature looks nicer, and I think it expresses better the "need" for T to "be" an instance of CanGreet, but there is a drawback: we lost the possibility to refer to our CanGreet implicit instance by a name.
To do so, in order to summon our instance from the implicit scope, we can use the implicitly function:

def greet[T: CanGreet](t: T): String = {
    val greeter: CanGreet[T] = implicitly[CanGreet[T]]
    greeter.sayHi(t)
}

To make it less cumbersome, you'll commonly see a companion object for type classes traits with an apply method:

object CanGreet {
    def apply[T](implicit C: CanGreet[T]): CanGreet[T] = C
}

It does exactly what we did in our last greet function implementation, allowing us to now re-write our greet function as follows:

def greet[T: CanGreet](t: T): String = CanGreet[T].sayHi(t)

CanGreet[T] is calling the companion object apply function (CanGreet[T] is in fact desugarized as CanGreet.apply[T]() with the implicit instance in scope passed to apply) to summon T's CanGreet instance from implicit scope and we can immediately use it in our greet function by calling .sayHi(t) on it.

Finally, you'll also probably see implicit classes, called syntax for our type class that holds the operation our type class permits:

implicit class CanGreetSyntax[T: CanGreet](t: T) {
    def greet: String = CanGreet[T].sayHi(t)
}

Allowing our greet function to be called in a more convenient, OOP method way:

geekocephale.greet

To sum up, here's all the code we wrote with these upgrades:

trait CanGreet[T] {
    def sayHi(t: T): String
}

object CanGreet {
    def apply[T](implicit C: CanGreet[T]): CanGreet[T] = C
}

implicit class CanGreetSyntax[T: CanGreet](t: T) {
    def greet: String = CanGreet[T].sayHi(t)
}

case class Player(nickname: String, level: Int)

object Player {
    implicit val playerGreeter: CanGreet[Player] = new CanGreet[Player] {
        def sayHi(t: Player): String = s"Hi, I'm player ${t.nickname}, I'm lvl ${t.level} !"
    }
}

Type classes bonus

A posteriori subtyping

Type classes have more to offer than classical OOP subtyping.

Type classes permit to add behavior to existing types (including types that are not yours):

import java.net.URL

implicit val urlGreeter: CanGreet[URL] = new CanGreet[URL] {
    override def sayHi(t: URL): String = s"Hi, I'm an URL pointing at ${t.getPath}"
}

We just added to java.net.URL the property of being able to say Hi !

Conditionnal interfacing

You can define conditionnal type class instances:

implicit def listGreeter[A: CanGreet]: CanGreet[List[A]] = new CanGreet[List[A]] {
    override def sayHi(t: List[A]): String = s"Hi, I'm an List : [${t.map(CanGreet[A].sayHi).mkString(",")}]"
}

By requiring [A: CanGreet], we just stated that List[A] in an instance of the CanGreet type class if and only if A is an instance of CanGreet.

Just to show you that we can push that conditional behavior further, we could have done something complety useless like:

implicit def listGreeter[A: CanGreet: MySndTypeClass](implicit c: MyThirdTypeClass[String]): CanGreet[List[A]] = ???

Here we request, for List[A] to be an instance of CanGreet, that:

A is instance of
- CanGreet
- MySndTypeClass
String is an instance of MyThirdTypeClass (which is, I have to admit, absolutly stupid).

Tooling

Simulacrum is an awesome library that helps tremendously reducing the boilerplate by using annotations that will generate the type classe and syntax stuff for you at compile time
Magnolia is a great library as well to automaticly derive your type classes instances

We did not talk about type classes derivation which is a bit more advanced topic, but the basic idea being that, if your types A and B are instances of a type class, and if you have a type C formed by combining A and B, such as:

case class C(a: A, b: B)

sealed trait C
case class A() extends C
case class B() extends C

It makes the type C automatically an instance of your type class !

More material

If you want to keep diving deeper, some interesting stuff can be found on my FP resources list and in particular:

Conclusion

So to conclude here, we saw why type classes are useful, what they are, how they are encoded in Scala and some cosmetics and tooling that might help you to work with them.

We went through:

How to create a class of types that provides shared behaviors
- Without having to know it beforehand (we don't extend our types nor modify them)
- Without having to mix that behavior to the data (the case class itself)
How to create new instances of our type class
How to leverage polymorphism by designing polymorphic functions defined and working for any type T as long as an (implicit) instance of it's required type class is provided !

I'll try to keep that blog post updated.
If there are any additions, imprecision or mistakes that I should correct or if you need more explanations, feel free to contact me on Twitter or by mail !

Edit: Thanks Jules Ivanic for the review :).