Type Classes

Sorting a list of Strings

List<String> list = ...
Collections.sort(list)
            

What happens if we don't (or can't) implement Comparable?

List<NotSortable> list = ...
Collections.sort(list, new Comparator<NotSortable>(){
  @Override
  public int compare(NotSortable a, NotSortable b) {
    return ...
  }
})
            

What about Scala?

List("a", "b").sorted
// Won't compile!
List(new NotSortable()).sorted;
            

Can't do this in Java

How does it work?

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

class List[T] {
  def sorted(implicit ordering: Ordering[T]): List[T]
}

List("a", "b").sorted
            

scalac -Xprint:typer

immutable.this.List.apply[String]("a", "b").sorted[Int](Ordering.String)
            

object Ordering {
  implicit object String extends Ordering[String] {
    def compare(x: String, y: String) = x.compareTo(y)
  }
}
            

Compile time only

List(1, 2, 3).sorted
// Doesn't compile
def sortList[A](list:List[A]) = list.sorted
// Need to 'pass around' the type class
def sortList[A](list:List[A])(implicit ord:Ordering[A]) = list.sorted
            

Slows down the compiler too :(

Are these not the same?

// Append numbers
def sum(list: List[Int])       = list.foldLeft(0) (_ + _)

// Append strings
def concat(list: List[String]) = list.foldLeft("")(_ + _)
            

trait Appender[T] {
  def zero: T
  def plus(a: T, b: T): T
}
            

Appender? Sounds lame.

What about a cool, mathematical name...

Something to drive fear into the hearts of Java programmers

Monoid - Fuck yeah!

trait Monoid[T] {
  def zero: T
  def plus(a: T, b: T): T
}
            

def sum[T](list: List[T])(implicit m: Monoid[T]): T = {
  list.foldLeft(m.zero)(m.plus)
}
            

implicit def int2monoid = new Monoid[Int] {
  def zero = 0
  def plus(a: Int, b: Int) = a + b
}
sum(List(1, 2, 3))

implicit def string2monoid = new Monoid[String] {
  def zero = ""
  def plus(a: String, b: String) = a + b
}
sum(List("a", "b", "c"))
            

Scala has Monoid. Sort of...

trait Numeric[T]
  // Sweet!
  def zero: T
  def plus(x: T, y: T): T

  // WTF?!?
  def minus(x: T, y: T): T
  def times(x: T, y: T): T
  def abs(x: T): T
  ...
}
            

You can't implement 'zero' with inheritance.

public <T extends Appender> append(List<T> list) {
  T last = null;
  for (T t : list) {
    if (list == null) {
      last = t;
    } else {
      last = last.append(t);
    }
  }
  return last;
}
            

Great talk:

Boring ol' List.map

List(1, 2, 3) map { _ + 1 }
// List[Int]

List(1, 2, 3) map { _.toString + "!" }
// List[String]
            

Pay close attention to the compiled type

The same for BitSet, almost...

import collection.immutable.BitSet

BitSet(1, 2, 3) map { _ + 1 }
// BitSet

BitSet(1, 2, 3) map { _.toString + "!" }
// Set[String]
            

WAT?!

What do we think map would look like?

class BitSet[A] {
  def map[B](f: A => B): BitSet[B]
}
            

What does map actually look like?

class List[A] extends GenTraversableLike[A, List]
class BitSet extends GenTraversableLike[Int, BitSet]
class GenTraversableLike[A, Repr] {
  def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That
}
            

scalac -Xprint:typer

val bits = BitSet(1, 2, 3)
bits.map[Int, BitSet](_ + 1)(BitSet.canBuildFrom)
bits.map[String, Set[String]](_.toString + "!")(Set.canBuildFrom[String])
            

object BitSet {
  implicit def canBuildFrom: CanBuildFrom[BitSet, Int, BitSet]
}
object Set {
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Set[A]]
}
            

class TraversableLike[A, Repr] {
  def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
    val b = bf(repr)
    b.sizeHint(this)
    for (x <- this) b += f(x)
    b.result
  }
}
            

Why?

Otherwise how can you:

1. Make a compile safe return type
2. Be influenced by generic type
3. Share as much generic code as possible

• Joonas Javanainen - Understanding the ++ operator
• Is the Scala 2.8 collections library a case of "the longest suicide note in history"?
• Programming in Scala - 2nd Edition

Why do we have to override/assume methods on Object?

• toString()
• hashCode()

Dangerous when it comes to inheritance

trait Show[A] {
  def show(a: A): String
}
def printMe[A](a: A)(implicit s: Show[A]) = "Showing " + s.show(a)
implicit def string2show = new Show[String] {
  def show(a: String) = a.toUpperCase;
}
printMe("Hello World")
// Doesn't compile
printMe(1)
            

class Parent {
  override def toString = "Parent only"
}
class Child extends Parent
implicit def a2show = new Show[A] {
  def show(a: A) = a.toString;
}
printMe(new Parent)
// Doesn't compile
printMe(new Child)