Practical Observations on Type Classes with Examples

Type Classes Some practical observations with examples

Robin Hillyard Associate Teaching Professor, College of Engineering, NEU scalaprof@gmail.com Comparer code: https://github.com/rchillyard/Comparer Table Parser code: https://github.com/rchillyard/TableParser Blog: http://scalaprof.blogspot.com Slides: see http://www1.coe.neu.edu/~rhillyard/

A bit of historical background In Java, we have the wholly bad Number. It ought (IMHO) to be an interface, but it is not: it s an abstract class. This means basically that you can t do much with it. It s essentially part of a fixed type hierarchy. When I started with Scala, I was thrilled to find that Numeric[T] was a trait. That meant that I could extend Numeric and add my own behavior to it. Not so fast! You still can t go around adding methods to your own sub-class of Numeric and have things like Int implement them. In that sense, we haven t improved much on Java.

Value I was trying to come up with a trait to extend Numeric[T] that implemented this essential method (at least, I thought it was essential): def fromString(s: String): T I asked a question on StackOverflow. The answer surprised me: just write your own type class. I hadn t realized that was even possible! What s a type class? Could I do that? And how could that help? So, I created a type class: trait Value[T] extends Numeric[T] { def fromString(s: String): T }

Type classeswhat exactly are they? Forget for the moment what Java means by class : that isn t really helpful here. A general, if technical, definition of class is a way of describing many things having some common trait(s) (small t ) or: Merriam-Webster defn. 3: a group, set, or kind sharing common attributes. A type is well, that s a tricky one. One might say that it s a constraint on a parameter of a function (including the return parameter ) if we didn t have functions, we wouldn t need types. For example, a Boolean type limits the number of possible values to two: true and false. So a type class is a group of types that share some behavior (property). The best-known type class is perhaps Ordering[T]. It basically describes a group of types which all define a method (function) with signature (T,T)=>Int and identifier compare.

But where do type classes come from? Type classes come from Haskell. Other functional, typed languages (such as Miranda) do not have the same richness of type construction and so don t need type classes. Essentially, they allow you to describe a type by logically defining all of the possible values. Since Haskell is a pure functional language (i.e. without the possibility of adding behavior through inheritance), type classes were the natural way to go. After all, types aren t very much different from values. Just as we can create an expression in value-space such as f(x), there s no reason we can t write F[X] in type-space. Right?

But where do type classes come from (2) Type classes are not really first-class things in Scala: there s no special keyword such as typeclass or anything like that. Type classes are constructed via a type constructor of the form: <trait-name> [ <type-name> ] So, is such a trait the same thing as a type class? No. Loosely speaking, it s the template that tells us how to construct a type class from a given type. This is important: trait + actual_type* -> type_class. If we want to construct a type class from trait A and type B, do we have to own A and B? just A? just B? No. None of the above. We can create a type class from any (suitable) trait and any type! * By actual type, I mean not a parametric type.

Whoa! That sounds like a lot of type classes! Yes. If there are M suitable traits and N types, that means there can be M * N type classes.* So, what s a suitable trait? What does a hypothetical trait T need? At least one parametric type (we ll refer to it as X but, obviously, it could be anything); at least one method where a parameter or return value is a X; there should be no variables (i.e. vals) defined (thus we can create a singleton object which will be our unique instance of T[X]. That s it. So, not every trait can be a type class but, if you look around at the various traits that you or others have defined, you ll probably find a lot that would be suitable. * actually, that s true for traits with one parametric type; if we allow two, then we could have M2 N type classes and so on.

An example The Hello World of type classes is Show: trait Show[T] { def show(t: T): String } Well, that s nice but couldn t we just mix that trait into our own type (i.e. use inheritance)? Sure we could. But what if we want to showa type that isn t our own? It s marked final and belongs to some library that we re using? How are we going to do that? Using type classes give us the ability to define ad hoc polymorphism.

Polymorphism via inheritance So, going back to the object-oriented way of providing polymorphism (adding functionality to types) Suppose that we were able to mix in our Show trait with every type that we wanted to be showable (forgetting for the moment that we don t have access to the source code for all these types) We d still have to come up with a name (and some location in a module) for each of the potentially MxN such types. Where would we define them? That s a lot of types. And, now, if we wanted the compiler to ensure that such-and-such a type did in fact inherit some behavior defined in trait T, we d have to use a type constraint in the definition of a method such as:

Doing it the O-O way trait ObjectOrientedShow { def show: String }object Show { def showSomething[U <: ObjectOrientedShow](u: U): String = u.show } Now, suppose we have two such traits trait ObjectOrientedShow1 { def show1: String }trait ObjectOrientedShow2 { def show2: String }object Show { def showSomething[U <: ObjectOrientedShow1 with ObjectOrientedShow2](u: U): String = u.show1 ++ u.show2 }

Its beginning to get a bit messy If you ve ever tried to do this sort of thing (I have), you soon begin to run into all sorts of complications. This is especially true in Java where inheritance is your only option. Scala has a very powerful syntax for constraining these sorts of types but it s not for the faint of heart! So, let s give up on that idea (behavior through inheritance) and follow where type classes take us.

Lets get this Show on the road Although you might imagine that it s still really hard to know where to put (and what to name) the constructed type class members, in fact Scala (and implicits) make all of this really easy. First, we do have a logical place where we can define all of these constructed types: it s in the companion object for the trait. object Show { val showInt: Show[Int] = newShow[Int] { def show(int: Int): String = s"int$int" } } And we could use it as follows: println(Show.showInt.show(42))

But, Scala makes it much easier/more elegant Recall that, if we want to apply the common behavior of the type class, e.g. in the case of Show[T], we want to invoke show(t), then we don t need to construct a new instance of, say, Show[Int]. Because there are no instance variables, one singleton object suffices. Great. Now, what s the easiest way of introducing a singleton instance of a particular type, in this case Show[Int] or T[X], that is, essentially, global? Make it implicit and put it in the companion object of either T or X, e.g. Show or Int*. The compiler will find it for us Awesome! * obviously, we can t put it in Int

And thats not all! There is a bit of syntactic sugar that makes it even easier. So, if we want to be able always to show a value in a class or method, we can simply add a context bound (strange name!) to the declaration of a parametric type: case class Node[T: Show](t: T) { def showNode: String = implicitly[Show[T]].show(t) } The context bound essentially forces the compiler to look for an implicit value of Show[T]. Another nice thing: you can have T conform to as many context bounds as you like.

More on Context Bounds Let s say that we have a method which will take an Int and return some numeric type T: def intToT[T: Numeric](x: Int): T = implicitly[Numeric[T]].fromInt(x) This is exactly equivalent (after desugaring) to: def intToT[T](x: Int)(implicit ev: Numeric[T]): T = implicitly[Numeric[T]].fromInt(x) Or: def intToT[T](x: Int)(implicit ev: Numeric[T]): T = ev.fromInt(x)

More on Context Bounds (part two) But what if our type T has more than one type class? No problem (you can have as many as you like): def showIntAsT[T: Numeric : Show](x: Int): String = implicitly[Show[T]].show(implicitly[Numeric[T]].fromInt(x)) Here s an example from a Monte Carlo Tree Search program: abstract class ExpandingNode[T: Expandable : GoalDriven : Ordering : Loggable]

Type classes with more than one parametric type? But what if a trait takes more than one parametric type? Can we still use it as a kind of type class? No problem (but we won t be able to use a Context Bound): trait TypeClass2[T, U] { def tToU(t: T): U } case class Y[T, U]()(implicit ev: TypeClass2[T, U]) { def z(t: T): U = ev.tToU(t) } implicit object TypeClass2StringInt extends TypeClass2[String, Int] { def tToU(t: String): Int = t.toInt }val y = Y[String, Int]()

So, enough background Sorting is something we need to do a lot. Let s say we have a date type: case class Date(y: Int, m: Int, d: Int) Following the Java style of sorting, we can have our classes implement the Ordered trait (via inheritance similar to implementing Comparable in Java): case class Date(y: Int, m: Int, d: Int) extends Ordered[Date] def compareTo(that: Date): Int = { val cfy = y.compareTo(that.y) if (cfy!=0) cfy else { val cfm = m.compareTo(that.m) if (cfm!=0) cfm else d.compareTo(that.d) } } Of course, we use the Java-style comparisons that Scala comes with. I don t like it. Do you? It s inelegant to say the least. But it s the standard pattern.

Type class Example First, let s appreciate the power of type classes when it comes to sorting (and other similar aspects of programming). We can improve a bit on the last code by using a built-in type class called Ordering. We implement the Ordering trait as a type class by defining an implicit object that implements Ordering in the companion object of the type that we want to sort on: trait OrderingDate extends Ordering[DateJ] { def compare(d1: Date, d2: Date): Int = { val cfy = d1.year.compareTo(d2.year) if (cfy != 0) cfy else { val cfm = d1.month.compareTo(d2.month) if (cfm != 0) cfm else d1.day.compareTo(d2.day) } } } implicit object OrderingDate extends OrderingDate I still don t like that compare method.

Back to our example: Lets make it more functional How do we compare objects functionally? What does that even mean? The essential pattern of comparison is: To test each pair of values of the primary key in turn, starting with the most significant. If the values are different, we return the difference; if the same, we continue with the next most significant pair, and so on. In functional programming, we d like to be able to compose comparers (Orderings, if you like) for the individual pairs: val orderingYear: Comparer[Date] = { t2 => { t1 => Comparison.compare(t1.year,t2.year)}} val orderingMonth: Comparer[Date] = {t2 => { t1 => Comparison.compare(t1.month,t2.month)}} val orderingDay: Comparer[Date] = {t2 => { t1 => Comparison.compare(t1.day,t2.day)}} val orderingDate: Comparer[Date] = orderingYear orElse orderingMonth orElse orderingDay

Lets make it more functional (2) Essentially, the definition of Comparer that we need for this is: trait Comparer[T] extends (T => T => Comparison) { self => def orElse(tc: => Comparer[T]): Comparer[T] = t1 => t2 => self(t1)(t2).orElse(tc(t1)(t2)) } Repeating our application code from the previous slide: val orderingYear: Comparer[Date] = { t2 => { t1 => Comparison.compare(t1.year,t2.year)}} val orderingMonth: Comparer[Date] = {t2 => { t1 => Comparison.compare(t1.month,t2.month)}} val orderingDay: Comparer[Date] = {t2 => { t1 => Comparison.compare(t1.day,t2.day)}} val orderingDate: Comparer[Date] = orderingYear orElse orderingMonth orElse orderingDay

Lets make it more functional (3) Notice that we ve essentially declared each Comparer by defining a lambda. This works because the definition of the apply method is the only method in Comparer[T] that is yet to be implemented all other methods have default implementations. So, we ve got three Comparersand we ve combined them using orElse. If we need to invert the meaning of the Comparer which is a parameter of orElse, we can use orElseNotinstead. It s so easy to compose these things!

Making it still more elegant The three definitions of Comparer are almost identical. Surely we can do some refactoring there? We can use the snap method of Comparer: val ic = implicitly[Comparer[Int]] val comparerY: Comparer[Date] = ic.snap(_.year) val comparerM: Comparer[Date] = ic.snap(_.month) val comparerD: Comparer[Date] = ic.snap(_.day) val comparer = comparerY orElse comparerM orElse comparerD Snaptakes a lens function, in these cases of type Date->Int, and yields a Comparer[Date]. Snap s signature is: def snap[U](lens: U => T): Comparer[U] snap is essentially the map/apply method of a Covariant Functor.

And yet more elegant Notice that we would have a hard time doing even this, if we didn t have type classes. We needed to pick up an implicit comparer of Int, which we did via the implicitly keyword. Here are some expressions that make that last version a little nicer: Comparer.same[Date] :| (_.year) :| (_.month) :| (_.day) Comparer[Date](_.year, _.month, _.day) The latter form applies if all the functions are of the same type (and no inversions). And, finally (the pi ce de r sistance): object MyComparers extends Comparers { val comparer: Comparer[Date] = comparer3(Date) } This last pattern is implemented the same way that we would define JSON formats. As long as the parameters of Date are types for which we have defined comparers (like Int) and/or are wrapped in Seq, List, Try or Option, etc., the compiler will do all the heavy lifting for us. Indeed, we are getting the benefit of TIM (type inference magic): we pass in the Date.apply method but we never actually use it inside comparer3(it s there solely for TIM).

A look under the hood Let s take a look at the code for this comparer3 method (its fellows all look similar): /** * Method to return a Comparer[T] where T is a 3-ary Product and which is based on a function to convert a P0,P1,P2 into a T. * * @param f a function (P0,P1,P2) => T, usually the apply method of a case class. * @tparam P0 the type of the first field of the Product type T. * @tparam P1 the type of the second field of the Product type T. * @tparam P2 the type of the third field of the Product type T. * @tparam T the underlying type of the result, a Product. * @return a Comparer[T] which can compare two instances of T and return a Comparison. */ def comparer3[P0:Comparer, P1:Comparer, P2:Comparer, T<:Product](f: (P0,P1,P2) => T): Comparer[T] = comparer[T, P0](0) orElse comparer[T, P1](1) orElse comparer[T, P2](2) private def comparer[T <: Product, P: Comparer](x: Int): Comparer[T] = Comparer.comparer[T, P](t => t.productElement(x).asInstanceOf[P])

A look under the hood continued Notice that all three P types define an implicit Comparer[P] (via context bound). Where would we be without type classes? The compare method is defined thus: def comparer[T, P: Comparer](lens: T => P): Comparer[T] = implicitly[Comparer[P]].snap(lens) Note: this version uses asInstanceOf in the private compare method. We can replace that with a match/exception but, in practice, it can only fail if there s a logic error in the Comparers module itself, not application code. Comparer, by the way, is best defined not as T => T => Int but as: T => T => Comparison Where Comparison is essentially the same as Option[Boolean].

When cant we use type classes? Let s say we have a collection of things and we want to be able to show each one: Trait ShowableCollection[T: Show] { def show = implicitly[Show[T]].show } That won t work because traits don t have constructors so they can t handle the implicit evidence of showability. This restriction is lifted in Dotty.

Typeclasses in Dotty Here s an example program: trait X[T](ev: Numeric[T]) { def show(t: T): String = ev.toDouble(t).toString } case class Xint() extends X[Int](implicitly[Numeric[Int]]) object Fred extends App { println(Xint().show(1) ) It doesn t appear to be possible to use a context bound here. But the (current) official way to define type classes is with given.

Any Questions?