Typeclasses for the Masses

class: center, middle, transition, intro

#  Typeclasses for the Masses

.caption[Daniel Beskin]
???
- In this talk we are going to discuss typeclasses
---
class: center, middle, transition

> All problems in programming can be solved by another typeclass
  <br />...except for the problem of too many typeclasses.

.footnote[― Old programming wisdom, slightly paraphrased]

???
- Typeclasses are a functional "design pattern" and a way to create abstractions
- It allows us to write extensible code at the right level of abstraction
- This pattern is very common in the Scala ecosystem
- Learning it will make various libraries easier to use
---
class: center, middle, transition

Looking for Motivation

.suicide[![](suicide.png)]

???
- First, a bit of motivation to get ourselves started
- The running example will be a generic sorting function
---
## Java-style, take #1 - Inheritance
```
trait Orderable[A] {
  def compare(that: A): Int
}

{{content}}
```

???
- Here's a naive Java style attempt
- We define an `Orderable` trait for things that can be sorted by our function

--
def sort[A <: Orderable](xs: List[A]): List[A]

{{content}}
???
- Given a list of `Orderable`s, we can use their `compare` method to sort them
- For example:
--

case class Clippy(annoyanceLevel: Int) extends Orderable[Clippy] {
  def compare(that: Clippy) = ???
}

???
- The problem with that approach is that it's not extensible
- If a type is not in our control, we can't make it `Orderable` after the fact
---

## Java-style, take #2 - Adapter

```
trait Ordering[A] {
  def compare(x: A, y: A): Int
}

{{content}}
```

???
- Taking out our design patterns book, the Adapter design pattern fits the bill
- It allows us to adapt existing classes to our new abstraction
- We now define `Ordering` as a standalone entity

--
def sort[A](xs: List[A], ord: Ordering[A]): List[A]

{{content}}
???
- Sorting now takes an adapter parameter
- And so we can now adapt any existing class to our `Ordering` abstraction

case class Clippy(annoyanceLevel: String)

val clippyOrdering = new Ordering[Clippy] {
  def compare(x: Clippy, y: Clippy) = ???
}

sort(List(c1, c2, c3), clippyOrdering)

???
- We now have an extensible ordering, but the usage is a bit clumsy, we have
to pass these `Ordering`s around
- Given that we use Scala, we can sprinkle some implicit magic to make it a bit
nicer to use

---
## Java-semi-Scala-style

```
def sort[A](xs: List[A])(implicit ord: Ordering[A]): List[A]
```

--
```
implicit val clippyOrdering = new Ordering[Clippy] {
  def compare(x: Clippy, y: Clippy) = ???
}

sort(List(c1, c2, c3))
```

.java[![](java.png)]
???
- Now we don't have to pass `Ordering`s around
- Once we make them implicit, the compiler will take care of passing them around for us
- And that's about 90% of typeclasses
- The typeclasses formalizes this pattern, and gives a bit more of a punch

---
class: center, middle, transition

Typeclasses - Definition

.tooling[![](tooling.png)]
???
- Now we are ready to actually define typeclasses

---
## Typeclasses - Definition

A class:
```
trait Ordering[A] {
  def compare(x: A, y: A): Int
}
```
???
- A typeclasses consists of a "class definition"
- Typically a trait, parameterized by a type variable, `A`
- With methods operating on `A`
- The terminonlogy comes from Haskell, where typeclasses are an actual specially supported language feature
- The word "class" here has nothing to do with OO-style classes
--

An instance:

```
implicit val clippyOrdering = new Ordering[Clippy] {
  def compare(x: Clippy, y: Clippy) = ???
}
```

???
- For a given class definition we can have many "instances"
- An instance is defined for a specific choice of the type parameter `A`
- An instance is provided as an implicit value or definition
- This is called "the Ordering instance for `Clippy`"
- What we are doing is declaring the fact that the type can be ordered, and tell the compiler how
- In other words: the `Clippy` type belongs to a class of types that have an `Ordering`
- Hence the name of the pattern: "typeclasses"

---
## Typeclasses at the Use-site

Generic functions:

```
def sort[A](xs: List[A])(implicit ord: Ordering[A]): List[A]

{{content}}
```
???
- We use typeclasses to define functions that are generic over the typeclass instance
- This can be rewritten as follows
--
def sort[A: Ordering](xs: List[A]): List[A]

???
- This is equivalent to the above line but better conveys our intent
- Which is: given that `A` has an instance of `Ordering`, that is it belong to the `Ordering` class, then we can define a sort for it
- The syntax is called a "context bound", meaning that we operate on `A`, given some context can be implicitly provided for `A`
--

Operator syntax:
```
implicit class OrderingOps[A: Ordering](a: A) {
  def <=(other: A) = ???
}

Clippy(2) <= Clippy(5)
```

???
- Since typeclasses are defined outside the objects that actually use them
- It's often use the pimp my type pattern to define operator syntax for instances of some classes
- This reads as follows: given that `A` has an instance of `Ordering`, we can use the following methods/operators on it
- Where inside the definitions will make some use of of the implicit typeclass instance that we have in scope

---

## Benefits
--

- Abstraction

???
- Code that we write against a typeclass instance can be very generic
- Since it works directly with an abstraction, it is precise, we don't have access to any information outside the abstraction
- This can lead to much code reuse, since a single definition can be applicable in many contexts
--

- Extensibility

???
- Unlike the inheritance based OO solution, typeclasses are extensible
- A type can be included in a class even after the type was defined
- This means that we can adapt old code to new use cases without modifying the code itself
--

- Type-driven
???
- The two previous items were also applicable to the `Adapter` pattern
- What we gain in make use of implicits, is the fact that the compiler can do some work for us
- We can think of implicits as a way to tell the compiler some information
- By creating an implicit `Ordering` for `Clippy`, we are telling the compiler that `Clippy` can be ordered
- The compiler can use this information to derive new facts from it, like how to make an `Ordering` for `List[Clippy]`
- For example
--

implicit def listOrd[A: Ordering]: Ordering[List[A]]

---
## Un-benefits

- Indirection

???

- Writing typeclasses-heavy code can lead to significant amount of indirection
- Which in some cases may not be appropriate and result in harder to code to read/maintain
- This may, also, sometimes have performance consequences (though we'll see  how to address it later on)

- No direct language support
.spell[![](spell.png)]

???

- Typeclasses, as a whole, are not a language feature, correspondingly, there isn't direct language support for it
- For example: there isn't special Scaladoc format for it, and the compilation errors may not be as informative as possible
--

- Implicit madness

???

- Last, since typeclasses make use of implicits, in some cases non-trivial logic can be encoded in the implicit resolution process
- Which can result in hard to decipher code and compilation errors.

---
class: center, middle, transition

Extended Example: Configuration Readers

.quip[![](quip.png)]
???

- Let's put typeclasses to use
- We will now try to write a small wrapper around Typesafe config to make it a bit more useable
---

## ~~Typesafe~~ Lightbend Config

```
config.getString("clippy.name")

config.getInt("clippy.annoyanceLevel")

config.getStringList("clippy.tips")

{{content}}
```

???
- Typesafe config is rather annoying, to get something out of it, we need to call a special method that matches the type
- The number of types is limited - only the one's defined by the library authors
- And the types themselves are not always nice to work with, like the Java collections that they return

get[String](config, "clippy.name")

get[Int](config, "clippy.annoyanceLevel")

get[List[String]](config, "clippy.tips")

???

- This is the function that we want to have
- We give it the type of thing that we want to fetch, and it fetches
- Note how this is a single function for all types
- But we want more, we want to be able to extend it with our own types
- For example
--

get[Clippy](config, "clippy")

???
- So what we want, is a "smart" function, that is open for extension by third parties
- This is perfect use case for typeclasses
---

## The Typeclass

```
trait ValueReader[A] {
  def read(config: Config, key: String): A
}

{{content}}
```

???
- This is the typeclass that we'll use
- Given some type `A`, it will give us the ability to read it from a config
- For example, here's the `Int` instance

implicit val intValueReader = new ValueReader[Int] {
  def read(config: Config, key: String): Int = config.getInt(key)
}

{{content}}
???
- This is just a wrapper around the original functionality
- We are adapting it to our new typeclass interface
- Similarly, we can define instances for all the built-in config getters
--

implicit val stringValueReader = new ValueReader[String] {
  def read(config: Config, key: String) = config.getString(key)
}

implicit val stringListValueReader = new ValueReader[List[String]] {
  def read(config: Config, key: Sting) =
    config.getStringList(key).asScala
}

???
- And similarly for other primitive types
- Note that here we already adapt the list to be a Scala `List`, so we already gained some adapting benefit
- Let's see how we define our getter function
---

## The Getter Function
```
def get[A: ValueReader](config: Config, key: String): A =
  implicitly[ValueReader[A]].read(config, key)

{{content}}
```
???
- This can be read as follows: given a `ValueReader` for `A`, a config and a key, fetch an `A`
- The implementation is straightforward
- First summon the implicit `ValueReader` for `A`, which must be present since we have a context bound in place
- Then read the value from the config using the reader
- Alternatively, we can drop the context bound and write the function with an implicit
- Like so

--
def get[A](config: Config, key: String)
          (implicit reader: ValueReader[A]): A =
  reader.read(config, key)

???
- So what have we gained from writing it this way?
- This solution is extensible, anyone can write a `ValueReader` for any type they want
- Like so

---

## More Readers

```
implicit val clippyReader = new ValueReader[Clippy] {
  def read(config: Config, key: String): Clippy =
    Clippy(name = get(config, s"$key.name"),
           annoyanceLevel = get(config, s"$key.annoyanceLevel"),
           tips = get(config, s"$key.tips"))
}

get[Clippy](config, "clippy")

{{content}}
```

???
- Notice that we don't need to specify the type on `get`, since the type here can be inferred from the context
- But we can do even fancier things, we can let the compiler do the hard work for us

---
## More Readers
```
implicit def optionValueReader[A: ValueReader] =
  new ValueReader[Option[A]] {
    def read(config: Config, key: String): Option[A] =
      if (config.hasPath(key)) Some(get[A](config, key))
      else None
  }

{{content}}
```
???
- As I mentioned previously, implicits are a way to communicate with the compiler
- And the compiler can derive new things for us
- Here's an example
- This can be read as: given that we know how to read a value of some type `A`
- Then we can automatically derive how to read a value of `Option[A]`
- And it can be used as follows

get[Option[Int]](config, "clippy.annoyanceLevel")

???
- Note that we don't have to do any special construction for the `ValueReader` for `Option`
- When the compiler sees the type `Option[Int]`, it automatically finds our `opitonValueReader` and `intReader`
- And then uses them to construct the right instance for `Option[Int]`, with no new code from our side
- We can do similar things for lists or maps
- Even fancier, we can right a generic `ValueReader` that will allow the compiler to build a reader for any case class
- Though for these kinds of things we'll need either macros or `Shapeless`

---
## Pimp My Config

```
implicit class ConfigOps(config: Config) {
  def get[A: ValueReader](key: String): A = get[A](config, key)
}

```

???
- It may feel a bit unnatural to use our `get` function, since it's not on `config`
- To remedy this, we can use the "pimp my type pattern" to make it nicer to use

--
```
config.get[Clippy]("clippy")
```
.pimp[![](pimp.png)]

???
- And now we can use it like so
- This concludes our example
- You may be pleased to know that this functionality and much more is available in the Ficus library

---
class: center, middle, transition

Typeclasses in the Wild

.exciting[![](exciting.png)]

???

- In this part, we will give a brief overview of the various typeclasses the exist in the Scala ecosystem
- Since typeclasses are present in many libraries, knowing this pattern might help when trying to use them
---
## Standard Typeclasses

???
- We will start with some basic typecalsses
- The reason I'm calling them standard is because they're inspired by typeclasses in Haskell's standard library
--

```
trait Equality[A] {
  def areEqual(a: A, b: A): Boolean
}
```

???
- This can be used to customize equality checks, beyond the standard `equals` method
- For example, ScalaTest, has equality matchers that use this to override the standard equals
- Since this is extensible, as library users, you can implement use it yourself by implementing special equality checks for your tests
- E.g., for testing JSON strings, ignoring the formatting
- Note that this function is safer than the regular `equals` since it uses `A` instead of `Any` as the parameters
--

```
trait Ordering[A] { ... }
```

???
- The `Ordering` that we already explored is defined in Scala's standard library and is used there

```
trait Numeric[A] {
  def fromInt(x: Int): A
  def abs(x: A): A
  ...
}
```

???
- This typeclass let's us write generic numeric code without thinking about the specific implementation
- It is present in Scala's standard library
- But it's quite slow for performance intensive code
- There's analogous code in the Spire library that should be very performant
- One can define many other numeric types, like fractional, in places where the full power of `Numeric` is not needed

---

## Parsing and Serialization

```
trait Writes[A] {
  def writes(a: A): JsValue
}

trait Reads[A] {
  def reads(json: JsValue): A
}
```

???
- Parsing and serialization is one of the most common use cases for typeclasses
- Since pretty much by definition it's an open world problem
- For example, Play! uses typeclasses for reading and writing JSON values for arbitrary types
- Just like in the `ValueReader` example, readers and writes can be automatically derived for complex types using definitions for basic types
- Play! has a macro that does that for case classes

---

## Algebra

```
trait Monoid[A] {
  def id: A
  def op(x: A, y: A): A
}

trait NRoot[A] {
  def nroot(a: A, n: Int): A
}

trait InnerProductSpace[V, F] {
  def dot(v: V, w: V): F
}
```

???
- There's a whole bunch of typeclasses that can be defined to capture various concepts in abstract algebra
- This is just a sample from the typeclasses available in Spire
- Although quite abstract these abstractions find their way into real code
- For example, the `Monoid` type captures the notion of things that can be aggregated in parallel
- This makes it the perfect abstraction for Map/Reduce
- And it's quite popular in the world of big-data, as such, it's actually defined in a number of different libraries
- One of the benefits of working with these abstract types is code reuse
--

```
def accumulate[A: Monoid](xs: List[A]): A =
  xs.foldLeft(id)(_ |+| _)
```

???
- For example, you can write generic code for some accumulation logic (like a fold) based on a `Monoid`
- The `|+|` operator is an alias for `op`
- This reads as: given a list of `A`s, where `A` has a `Monoid` instance
- Fold the list, and use the `Monoid` operation to combine the values into a single value
- And the very same code can work for any type that has an instance of `Monoid`
- And there are many types that can be viewed as monoids: numbers, strings, maps, etc.

---

## Abstract Nonsense

???

- Last, but definitely not least, are the typeclasses that come from the world of category theory
- Just like the algebraic typeclasses, these abstraction can be very useful in programming
- We'll briefly review a couple of types, but they deserve a number of talks of their own
--

```
trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}
```

???

- `Functor` represents things that can be mapped over, like list, futures, etc.
- We can think of `F[_]` as some kind of context in which we are mapping
- So a list or a future is a kind of context in which we perform a computation

```
trait Applicative[F[_]] extends Functor[F] {
  def unit[A](a: A): F[A]
  def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
}
```
???

- `Applicative` gives us a `map` on steroids
- `map2` lets us combine values inside a context
- This might be somewhat abstract, but the weird operators that we use with `Validation` are defined in terms of `Applicative`
- In this case `Validation` is the context and `map2` let's us build complicated objects from validated parts
- Let's look at an example of a useful function that can be written in terms of `Applicative`

.monads1[![](monads_1.png)]

---

## Using Applicatives

```
def sequence[F[_]: Applicative, A](fs: List[F[A]]): F[List[A]]

{{content}}
```

???
- This function can be read as: given a list of things in an applicative context
- Create a list of things and put the whole list inside the context
- You may be familiar with something similar: the `sequence` function on `Future` in the standard library
- This one is a generalization that works for anything that has an `Applicative` instance
- Like `Option`s, `Validation`s and whatnot
- We need to write it once in term of `Applicative` and we get all these use cases for free
- Here's the implementation

def sequence[F[_], A](fs: List[F[A]])
                     (implicit ap: Applicative[F]): F[List[A]] =
  fs match {
    case Nil => ap.unit(Nil)
    case fa :: rest => ap.map2(fa, sequence(rest))(_ :: _)
  }

???
- It's a bit tricky, but if you just follow the types, it kind of writes itself
- Figuring out how it works is left as an exercise
- And here's a usage example
--

```

sequence(List(Option(1), Option(2), Option(3))
// => Some(List(1, 2, 3))

sequence(List(Option(1), None, Option(3)))
// => None
```

.monads2[![](monads_2.png)]

???
- This will work given that we actually defined an `Applicative` instance for `Option`
- Similarly, we can apply `sequence` to `Future` or `Validation`
- `Functor`, `Applicative` and many others are available in Scalaz and Cats
- This concludes our overview of typeclasses in the ecosystem

---
class: center, middle, transition

Extras

.captive[![](captive.png)]

???

- We are almost done
- As a finishing touch, we'll touch upon a couple of advanced libraries that make the usage of typeclasses a bit more pleasant
---

## Simulacrum

```
import simulacrum._

@typeclass trait Monoid[A] {
  @op("|+|") def op(x: A, y: A): A
}

{{content}}
```

???
- As you might have noticed, defining a new typeclass is a bit boilertlaty
- We need to both define a trait for the typeclass and a class for the implicit operations
- The Simulacrum library let's you cut down on the boilerplate by using a macro annotation
--

implicit val clippyMonoid: Monoid[Clippy] = ???

Clippy(5) |+| Clippy(4)
???
- With this definition, we define a single trait and get both the typeclass definition and the implicit operators generated for us
- And we can use it for anything that implements the typeclass
- This is almost half way towards language support
---

## Machinist

```
import machinist.DefaultOps

trait Equality[@specialized A] {
  def eqv(lhs: A, rhs: A): Boolean
}

object Equality {
  implicit val intEq = new Eq[Int] {
    def eqv(lhs: Int, rhs: Int): Boolean = lhs == rhs
  }

implicit class EqOps[A](x: A)(implicit ev: Eq[A]) {
    def ===(rhs: A): Boolean = macro DefaultOps.binop[A, Boolean]
  }
}

{{content}}
```

???
- Also of note about typeclasses, is that all of the indirection that is used between the actual operation and the typeclass definition may incur a performance cost
- This is may be especially important in cases where typeclasses are used for numerics
- The Machinist library provides a macro that can cut down this cost
- As we see in this example, we are defining an equality typeclass
- When we define an operator for it, `===` we use the Machinist macro instead of writing it ourselves

--
object Test {
  import Eq.EqOps

def test(a: Int, b: Int)(implicit ev: Eq[Int]): Int =
    if (a === b) 999 else 0
}

// if (Eq.intEq.eqv$mcI$sp(a, b)) 999 else 0

???
- At the use-site, the macros unwraps all the indirection levels and the final result compiles to an unboxed equality of two integers
- This is what the Spire library uses behind the scenes to achieve fast generic code

---
## Shapeless's Typeclass Derivation

```
import spire.implicits._
import shapeless.contrib.spire._

case class Clippy(annoyanceLevel: Int, persistence: Int)
```
???
- Some typeclasses can be derived mechanically given some case class or a sealed case class hierarchy
- Examples include some of the standard typeclasses, monoids and Functors
- Shapeless provides some machinery to generate the typeclass instances for us
- And the library Shapless-contrib provides the machinery for some common typeclasses
- In  this example by just using some magic imports, we automatically able to derive an `AdditiveMonoid` for `Clippy`

--
```

Clippy(5, 3) + Clippy(3, 4) // => Clippy(8, 7)
```

???
- So without ever defining the `+` operator for it, we get and it does the right thing

---
class: center, middle, transition

FIN

.pop[![](pop.png)]