typeclasses-draft

typeclasses.md

title	author	patat
Getting Func-ey	Mathew Fournier	theme images syntaxHighlighting decVal bold backend auto

Typeclasses

Why?

• they allow us to extend libraries with new functionality
• they do not use traditional inheritance (subtyping), even though there is kind of a hierarchy of inheritance
• you can add new functionality w/o changing original source code
  • see expression problem

---

Typeclasses - Interfaces

People will try to say that Interfaces are like typeclasses. While there are some similarities, it's not really true. See:

• typeclasses are nothing like interfaces
• how to typeclasses differe from interfaces
• typeclasses in translation

tldr:

• separation of implementation (we'll get to this)
• return type polymorphism (not in scope of this talk)

---

Typeclass

A typeclass is a trait that:

• holds no state
• has a type parameter
• has at least one abstract method
• may contain generalized methods
• may extend other typeclsases

There should be only one implementation of a typeclass for any given type parameter

• this is known as typeclass coherence
• scala will let you define more than one, but if they are both in scope == compile error
• having more than one is a bad design

---

Typeclass comprehensibility

• FP programers will rant about "lawless type classes" online

• type class "laws" are a statement about properties that must hold for a typeclass to be valid

• the Monoid typeclass has laws:

  • the binary operation must be associative:
    • combine(x, combine(y,z)) == combine(combine(x, y), z)
  • the idenity must be commutative:
    • combine(a, identity) == a == combine(identiy, a)

• the laws help us implement systems with many type classes, since it helps us know what to expect.

  • this is important, as typeclasses can derive other typeclasses at compile time!

---

Typeclasses - you see this all the time

You see these everywhere in Scala. For example, scala.math.Numeric:

trait Ordering[T] {
  def compare(x: T, y: T): Int
  def lt(x: T, y: T): Boolean = compare(x, y) < 0
  def gt(x: T, y: T): Boolean = compare(x, y) > 0
}

trait Numeric[T] extends Ordering[T] {
  def plus(x: T, y: T): T
  def times(x: T, y: T): T
  def negate(x: T): T
  def zero: T
  def abs(x: T): T = if (lt(x, zero)) negate(x) else x
}

---

Typeclass - Using

def signOfTheTimes[T](t: T)(implicit N: Numeric[T]): T = {
  import N._
  times(negate(abs(t)), t)
}

Ignoring the (for now) horrible syntax:

• we no longer have an OOP hierarchy for our input types
• our type no longer "is a" Numeric

---

Typeclass - Cleaning up

def signOfTheTimes[T: Numeric](t: T): T = {
    val ev = implicitly[Numeric[T]]
    ev.times(ev.negate(ev.abs(t)), t)
}

- this is a bit better.  the `T: Numeric` is a _context bound_
- the signature reads "give me any T that has a Numeric"

---

Typeclass - Cleaning up

• We can clean this up more by introducing a "summoning implicit" on the companion object

// this is just annoying boilerplate
object Numeric {
  def apply[T](implicit numeric: Numeric[T]): Numeric[T] = numeric
}

and now signOfTheTimes looks like:

```scala
def signOfTheTimes[T: Numeric](t: T): T = {
  val N = Numeric[T]
  import N._
  times(negate(abs(t)), t)
}

• but this kind of sucks (inside out static methods vs class methods)

---

Typeclass - Ops

It's common to introduce an ops on the typeclass companion:

object Numeric {
  def apply[T](implicit numeric: Numeric[T]): Numeric[T] = numeric

  object ops {
    // this is useful to add methods to a class in general
    // google extension methods
    implicit class NumericOps[T](t: T)(implicit N: Numeric[T]): {
      def +(o: T): T = N.plus(t, o)
      def *(o: T): T = N.times(t, o)
      ...
      def abs: T = N.abs(t)
      ..
    }
  }
}

and now our signOfTheTimes looks like:

import Numeric.ops._
def signOfTheTimes[T: Numeric](t: T): T = -(t.abs) * t

---

Typeclass Monoid

trait Monoid[A] {
  // has an identity
  def empty: A
  // has an associative operation
  def combine(x: A, y: A): A
}

an implementation for the string type:

implicit val stringMonoid: Monoid[String] = new Monoid[String] {
  val empty = ""
  def combine(x: String, y: String): String = x + y
}

an implentation for Int type

implicit val intMonoid: Monoid[Int] = new Monoid[Int] {
  val empty = 0
  def combine(x: String, y: String): String = x + y
}

---

Typeclass composition

Here's where typeclasses start to get interesting:

• What if I want a Monoid for Options?
• I don't want to write out a monoid for Option[Int], Option[String], etc.
• how do I write a monoid for Option[A]?

implicit def optionMonoid[A](implicit am: Monoid[A]): Monoid[Option[A]] = {
  val o = new Monoid[Option[A]] {
    val empty = None
    def combine(x: Option[A], y: Option[A]): Option[A] = (x, y) match {
      case (None, None)       => None
      case (Some(_), None)    => x
      case (None, Some(_))    => y
      case (Some(x), Some(y)) => Some(am.combine(x,y)) // use the A monoid to combine two A's
    }
  }
}

• this is wild! I don't need to explicitly define Monoid[Option[Int]] if I have defined Monoid[Int]

• very different than an interface

• we define the base elements and the composition rules

  • at compile time, the compiler applies the composition rules
  • compiler constructs the type class instances we need

---

Typeclasses vs interfaces (records of functions)

I was asking all over twitter, gitter, IRC about when to use a typeclass vs when to use an interface. Someone kindly wrote a blogpost to answer this for me:

• if automatic composition will be useful then consider a typeclass
• if semantics are not well defined then don't use a typeclass
  • this is where people talk about typeclass laws
  • Monoid has laws
• if multiple instances are likely a typeclass is probably the wrong choice
• if it will make your code substantially easier to use a typeclass, it might be the right choice
  • API ergonomics

see: https://noelwelsh.com/posts/2019-06-24-type-classes-vs-record-of-functions.html

---

Typeclasses composition++

implicit def functionMonoid[A, B](implicit bm: Monoid[B]): Monoid[A => B] =
  new Monoid[A => B] {

    def empty: A => B = _ => bm.empty

    def combine(x: A => B, y: A => B): A => B = { a =>
      bm.combine(x(a), y(a))
    }
  }

given a monoid for B I can give you a monoid for fns returning B

---

Typeclasses, monoids, and fizzbuzz

<< scala cats example here >>

WTF!

---

Monoids and Folding

implicit def foldRight[A](la: List[A])(implicit am: Monoid[A]): A = {
  la.foldRight(am.empty)(am.combine)
}

---

Folding and constructor replacement

Remember that a string is just defined with a cons (constructor) arguement:

List(1,2,3,4) == 1 :: 2 :: 3 :: 4 :: Nil  // this is valid scala

foldRight is just constructor replacement with some f, and replacing Nil with empty

List(1,2,3,4).foldright(empty)((a, acc) => a `f` acc)

becomes

1 `f` 2 `f` 3 `f` 4 `f` empty

e.g.

List(1,2,3,4).foldRight(0)(_ + _)

1 + (2 + (3 + (4 + 0)))
// remember symetry
1 :: 2 :: 3 :: 4 :: Nil

So in our example (see whiteboard)