October 12, 2013

Introduction to Typeclasses in Scala

A little typeclass example, taken from original source here. The tut output is kind of noisy but I think overall it’s probably a win.

The challenge is to factor out the commonality here:

scala> def sum(ns: List[Int]): Int = ns.foldRight(0)(_ + _)
sum: (ns: List[Int])Int

scala> def all(bs: List[Boolean]): Boolean = bs.foldRight(true)(_ && _)
all: (bs: List[Boolean])Boolean

scala> def concat[A](ss: List[List[A]]): List[A] = ss.foldRight(List.empty[A])(_ ::: _)
concat: [A](ss: List[List[A]])List[A]

Some examples

scala> sum(List(1, 2, 3))
res0: Int = 6

scala> all(List(true, false, true))
res1: Boolean = false

scala> concat(List(List('a', 'b'), List('c', 'd')))
res2: List[Char] = List(a, b, c, d)

In each example we have a call to foldRight (which works on any List), using a “zero” value and a combiner function that are specific to the list’s element type. So let’s factor out the type-specific part:

scala> trait Combiner[A] {
     |   def combine(a: A, b: A): A
     |   def zero: A
     | }
defined trait Combiner

With that, we can now factor out the common functionality:

scala> def genericSum[A](as: List[A], c: Combiner[A]): A =
     |   as.foldRight(c.zero)(c.combine)
genericSum: [A](as: List[A], c: Combiner[A])A

Let’s define a combiner for Ints, using addition as our operator:

scala> val intCombiner = new Combiner[Int] {
     |   def combine(a: Int, b: Int) = a + b
     |   def zero = 0
     | }
intCombiner: Combiner[Int] = $anon$1@248a5f5e

scala> genericSum(List(1, 2, 3), intCombiner)
res3: Int = 6

So genericSum works for any type at all, as long as you supply an appropriate Combiner for that type. This is the typeclass pattern: Combiner is the typeclass, and the genericSum method demands evidence that A has an associated instance.

Typeclass parameters are usually implicit, so let’s rewrite a little:

scala> def genericSum2[A](as: List[A])(implicit c: Combiner[A]): A =
     |   as.foldRight(c.zero)(c.combine)
genericSum2: [A](as: List[A])(implicit c: Combiner[A])A

Let’s make our instance implicit, and declare another one:

scala> implicit val IntCombiner = intCombiner // from above
IntCombiner: Combiner[Int] = $anon$1@248a5f5e

scala> implicit val BooleanCombiner = new Combiner[Boolean] {
     |   def combine(a: Boolean, b: Boolean): Boolean = a && b
     |   def zero = true
     | }
BooleanCombiner: Combiner[Boolean] = $anon$1@56a82304

scala> genericSum2(List(1, 2, 3))
res4: Int = 6

scala> genericSum2(List(true, false, true))
res5: Boolean = false

Ok this is pretty nice. We now have a generic function for summing stuff, we can only call it if there’s an associated Combiner, and it has the correct static type. Try it with a List[String] and it won’t compile.

genericSum2(List("foo", "bar", "baz"))) // won't compile

We can even use an implicit class to add this functionality as syntax. Because the Combiner instance in the constructor is implicit, it’s also implicit in the body of the class.

scala> implicit class CombinerSyntax[A](as: List[A])(implicit c: Combiner[A]) {
     |   def gsum: A = genericSum2(as) // c will be passed along because it's implicit here
     | }
defined class CombinerSyntax

scala> List(1, 2, 3).gsum
res6: Int = 6

scala> List(true, false, true).gsum
res7: Boolean = false

But note that we never actually use c in the definition of CombinerSyntax; it’s just there in order to be introduced to the implicit scope. For cases like this there is a shortcut syntax called a context bound.

scala> implicit class CombinerSyntax2[A: Combiner](as: List[A]) {
     |   def gsum2: A = genericSum2(as) // unnamed Combiner[A] is implicit here
     | }
defined class CombinerSyntax2

Let’s create our List combiner. Note that this needs to be a def (not a val) because it has a type parameter. The compiler will call this method for us (!)

scala> implicit def ListCombiner[A] = new Combiner[List[A]] {
     |   def combine(a: List[A], b: List[A]): List[A] = a ::: b
     |   def zero = List.empty[A]
     | }
ListCombiner: [A]=> Combiner[List[A]]

And try it with the new syntax!

scala> List(List('a', 'b'), List('c', 'd')).gsum2
res8: List[Char] = List(a, b, c, d)

While we’re at it, let’s add syntax for any combinable A as well!

scala> implicit class ASyntax[A](a: A)(implicit c: Combiner[A]) {
     |   def |+|(b: A) = c.combine(a, b)
     | }
defined class ASyntax

scala> 1 |+| 2
res9: Int = 3

scala> true |+| true |+| false
res10: Boolean = false

scala> List(1, 2) |+| List(3, 4)
res11: List[Int] = List(1, 2, 3, 4)

Ok this is where it gets crazy. If we have a Combiner[A] and a Combiner[B] can we make a Combiner[(A,B)]? I say we can, and the compiler will use this to construct Combiner[(A, B)] for any A and B that can be combined.

scala> implicit def PairCombiner[A, B](implicit ca: Combiner[A], cb: Combiner[B]): Combiner[(A, B)] =
     |   new Combiner[(A, B)] {
     |     def combine(a: (A, B), b: (A, B)): (A, B) = (a._1 |+| b._1, a._2 |+| b._2)
     |     def zero: (A, B) = (ca.zero, cb.zero)
     |   }
PairCombiner: [A, B](implicit ca: Combiner[A], implicit cb: Combiner[B])Combiner[(A, B)]

scala> (1, true) |+| (2, true) |+| (3, true)
res12: (Int, Boolean) = (6,true)

scala> (List('a', 'b'), 5) |+| (List('d', 'e'), 10)
res13: (List[Char], Int) = (List(a, b, d, e),15)

Note that summing now works for list of combinable pairs!

scala> List((1, 2), (3, 4)).gsum
res14: (Int, Int) = (4,6)

But because we can combine pairs, pairs are combinable. So we can combine nested pairs too! WOW

scala> val a = (1, ((true, 7), List('a', 'b')))
a: (Int, ((Boolean, Int), List[Char])) = (1,((true,7),List(a, b)))

scala> val b = (9, ((true, 8), List('c', 'd')))
b: (Int, ((Boolean, Int), List[Char])) = (9,((true,8),List(c, d)))

scala> a |+| b
res15: (Int, ((Boolean, Int), List[Char])) = (10,((true,15),List(a, b, c, d)))

Ok that’s it for now. A few final notes: