Scala eXchange 2014 — London
Julien Sirocchi @jsirocchi
Senior Software Developer @ Workday
Scala, Akka, Play and Spray are in the Grid's team current toolbox
Follow us on Twitter @WorkdayDev and
checkout also our blog workday.github.io
No, not really
This talk is more a distilled narration of the long journey that I've experienced while discovering typeclasses in Scala
scala> val sorted = List(3, 1, 4, 2).sorted
sorted: List[Int] = List(1, 2, 3, 4)
Int extends java.lang.Comparable[Int]
?
sorted
work for
any type
of element A
in a List[A]
?
Int extends java.lang.Comparable[Int]
From the Scala 2.11.4 source code:
/** `Int`, a 32-bit signed integer (equivalent to Java's `int` primitive type) is a
* subtype of [[scala.AnyVal]]. Instances of `Int` are not
* represented by an object in the underlying runtime system.
*
* There is an implicit conversion from [[scala.Int]] => [[scala.runtime.RichInt]]
* which provides useful non-primitive operations.
*/
final abstract class Int private extends AnyVal {
// a bunch of abstract definitions to follow...
}
No polymorphism by inheritance here...
sorted
on any List[A]
Define some custom type A
scala> case class MyClass(x: Int)
defined class MyClass
Invoking sorted
on a List[MyClass]
scala> val sorted = List(MyClass(2), MyClass(1), MyClass(3)).sorted
<console>:9: error: No implicit Ordering defined for MyClass.
val sorted = List(MyClass(2), MyClass(1), MyClass(3)).sorted
...fails to even compile!
sorted
method defined in SeqLike[+A, +Repr]
def sorted[B >: A](implicit ord: Ordering[B]): Repr
sorted
does take a parameter, which can be implicitly
provided
B
and Ordering[B]
implicit
is a keyword
case class Person(name: String)
def hi(p: Person): String = s"""Hello ${p.name}!"""
implicit def string2person(s: String): Person = Person(s)
scala> hi("Julien")
res0: String = Hello Julien!
implicit class Person(val name: String) {
def greetMe: String = s"""Hello $name!"""
}
scala> "Julien".greetMe
res0: String = Hello Julien!
def add(a1: Int)(implicit a2: Int) = a1 + a2
implicit val one: Int = 1
scala> add(22)
res0: Int = 23
Ordering[T]
definition:
@annotation.implicitNotFound(msg = "No implicit Ordering defined for ${T}.")
trait Ordering[T] extends Comparator[T] with PartialOrdering[T]
with Serializable {
// implementation
}
Ordering[T] extends java.util.Comparator[T]
@implicitNotFound
is what is generating the error message
we saw earlier
Ordering[Int]
argument was implicitly provided
Ordering[Int]
is used by sorted
to
sort Int
elements
Ordering[A]
we can sort any
List[A]
Either explicitly...
scala> case class MyClass(x: Int)
defined class MyClass
scala> val orderingMyClass = new Ordering[MyClass] {
| override def compare(first: MyClass, second: MyClass): Int =
| if (first.x < second.x) -1
| else if (first.x == second.x) 0
| else 1
| }
orderingMyClass: Ordering[MyClass] = $anon$1@3c160f0f
scala> val sorted = List(MyClass(2), MyClass(1), MyClass(3))
.sorted(orderingMyClass)
sorted: List[MyClass] = List(MyClass(1), MyClass(2), MyClass(3))
It works!
...or implicitly
scala> case class MyClass(x: Int)
defined class MyClass
scala> implicit val orderingMyClass = new Ordering[MyClass] {
| override def compare(first: MyClass, second: MyClass): Int =
| if (first.x < second.x) -1
| else if (first.x == second.x) 0
| else 1
| }
orderingMyClass: Ordering[MyClass] = $anon$1@3c160f0f
scala> val sorted = List(MyClass(2), MyClass(1), MyClass(3)).sorted
sorted: List[MyClass] = List(MyClass(1), MyClass(2), MyClass(3))
It works too!
scala> val sum = List(1, 2, 3).sum
sum: Int = 6
Does this work similarly to sorted
?
Definition of sum
in TraversableOnce[+A]
def sum[B >: A](implicit num: Numeric[B]): B = foldLeft(num.zero)(num.plus)
Looks familiar, uh?
Numeric[T]
definition
trait Numeric[T] extends Ordering[T] {
def plus(x: T, y: T): T
def fromInt(x: Int): T
def zero = fromInt(0)
// more definitions
}
Numeric[T]
looks very similar to Ordering[T]
i.e. it works using the same machinery
Given any type A
, if the compiler can discover an instance of
Ordering[A]
, we can use A
in any method that implicitly
requires Ordering[A]
— or, in other words —
We can make our type A
behave as if it was an Ordering[A]
as long as we can implicitly provide an instance of Ordering
for our type
A
.
This is called ad-hoc polymorphism and it enables retroactive extensions.
Transforming a List[MyClass]
into a List[String]
.
scala> val sortedStrings = sorted.map(instance ⇒ instance.x.toString)
sortedStrings: List[String] = List(1, 2, 3)
Easy peasy! We all love that map
method, right?
Any idea of how that map
is defined in TraversableLike[+A, +Repr]
?
You may presume that its signature looks like
def map[B](f: A ⇒ B): Traversable[B]
def map[B, That](f: A ⇒ B)(implicit bf: CanBuildFrom[Repr, B, That]): That
An implicitly available CanBuildFrom[Repr, B, That]
?
Could that be a more sophisticated variation of what we have just seen?
What is Repr
? TraversableLike[+A, +Repr]
defines it
/** A template trait for traversable collections of type `Traversable[A]`.
* [...]
* @tparam A the element type of the collection
* @tparam Repr the type of the actual collection containing the elements.
* [...]
*/
trait TraversableLike[+A, +Repr] // some mixins and implementation details
And, since List[A]
is a TraversableLike[A, List[A]]
,
then in our example Repr
is List[MyClass]
scala> val l = List(MyClass(2), MyClass(1), MyClass(3))
l: List[MyClass] = List(MyClass(2), MyClass(1), MyClass(3))
scala> l.isInstanceOf[collection.TraversableLike[MyClass, List[MyClass]]]
res0: Boolean = true
From CanBuildFrom.scala
/** A base trait for builder factories.
*
* @tparam From the type of the underlying collection that requests
* a builder to be created.
* @tparam Elem the element type of the collection to be created.
* @tparam To the type of the collection to be created.
* [...]
*/
@implicitNotFound(msg = "Cannot construct a collection of type ${To} with
elements of type ${Elem} based on a collection of type ${From}.")
trait CanBuildFrom[-From, -Elem, +To] {
// method definitions
}
When invoking map
there has to be an implicit
CanBuildFrom[Repr, B, That]
, where:
Repr
is inferred as List[MyClass]
B
is inferred as String
What is That
? It represents the type of collection that will be
created. The List
companion object defines a
object List extends SeqFactory[List] {
/** $genericCanBuildFromInfo */
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, List[A]] =
ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]
// rest of the implementation...
}
Which means that we can
scala> implicitly[CanBuildFrom[List[Int], String, List[String]]]
res0: scala.collection.generic.CanBuildFrom[List[Int],String,List[String]] =
scala.collection.generic.GenTraversableFactory$$anon$1@28bfd1a8
What we've discovered so far are a couple of examples of typeclasses in Scala.
In computer science, a type class is a type system construct that supports ad hoc polymorphism. This is achieved by adding constraints to type variables in parametrically polymorphic types. Such a constraint typically involves a type classT
and a type variablea
, and means thata
can only be instantiated to a type whose members support the overloaded operations associated withT
.
I found Daniel Westheide's explanation on his The Neophyte's Guide to Scala much more readable
A type classTC
defines some behaviour in the form of operations that must be supported by a typeA
for it to be a member of type classTC
. Whether the typeA
is a member of the type classTC
is not inherent in the type. Rather, any developer can declare that a type is a member of a type class simply by providing implementations of the operations the type must support. Now, onceA
is made a member of the type classTC
, functions that have constrained one or more of their parameters to be members ofTC
can be called with arguments of typeA
.
To carve and use your own typeclass in Scala you need to define:
A
, which the compiler
can find in the implicit scope
That's it. Nothing more, really.
I'd recommend you doing:
@implicitNotFound
annotation on the
definition of your typeclass and provide a self-explanatory error message
trait TC[T] { def methodX(t: T): Int }
// provide the following apply, so that you can write: TC[T].methodX(...)
object TC { def apply[T : TC]: TC[T] = implicitly[TC[T]] }
Reason: need an algebra for simple expressions, which can be
sealed trait Expression
case class Value(value: Int) extends Expression
case class Add(expr1: Expression, expr2: Expression) extends Expression
case class Subtract(expr1: Expression, expr2: Expression) extends Expression
object Json {
def json(e: Expression): String = e match {
case Value(value) ⇒ s"$value"
case Add(e1, e2) ⇒ s"""{ op: "+", expr1: ${json(e1)}, expr2: ${json(e2)} }"""
case Subtract(e1, e2) ⇒ s"""{ op: "-", expr1: ${json(e1)}, expr2: ${json(e2)} }"""
}
}
object Evaluator {
def evaluate(e: Expression): Int = e match {
case Value(value) ⇒ value
case Add(e1, e2) ⇒ evaluate(e1) + evaluate(e2)
case Subtract(e1, e2) ⇒ evaluate(e1) - evaluate(e2)
}
}
If this code is part of a library its behaviour cannot be changed
scala> val expression =
| Add(
| Subtract(
| Value(10),
| Value(2)
| ),
| Add(
| Value(1),
| Value(2)
| )
| )
expression: Add = Add(Subtract(Value(10),Value(2)),Add(Value(1),Value(2)))
scala> val jsonString = Json.json(expression)
jsonString: String = { op: "+", expr1: { op: "-", expr1: 10, expr2: 2 }, expr2: { op: "+", expr1: 1, expr2: 2 } }
scala> val evaluated = Evaluator.evaluate(expression)
evaluated: Int = 11
sealed trait JsValue
case object JsNull extends JsValue
case class JsString(s: String) extends JsValue
case class JsNumber(i: BigDecimal) extends JsValue
case class JsBoolean(b: Boolean) extends JsValue
case class JsArray(a: Seq[JsValue]) extends JsValue
case class JsObject(m: Map[String, JsValue]) extends JsValue
Then we could have a Json
singleton object responsible for converting
a JsValue
into a String
, like
object Json {
def stringify(jsValue: JsValue): String = jsValue match {
case JsNull ⇒ "null"
case JsString(s) ⇒ s""""$s""""
case JsNumber(i) ⇒ s"$i"
case JsBoolean(b) ⇒ s"$b"
case JsArray(a) ⇒ (a map stringify).mkString("[ ", ", ", " ]")
case JsObject(m) ⇒
(for ((key, value) ← m) yield s"$key: ${stringify(value)}")
.mkString("{ ", ", ", " }")
}
object Json {
def stringify(jsValue: JsValue): String = // as before
def toJson(e: Expression): JsValue = e match {
case Value(value) ⇒ JsNumber(value)
case Add(e1, e2) ⇒ JsObject {
Map(
"op" → JsString("+"),
"expr1" → toJson(e1),
"expr2" → toJson(e2)
)
}
case Subtract(e1, e2) ⇒ JsObject {
Map(
"op" → JsString("-"),
"expr1" → toJson(e1),
"expr2" → toJson(e2)
)
}
}
}
scala> val json = Json.toJson(expression)
json: JsValue = JsObject(Map(operation -> JsString(+), expression1 -> JsObject(Map(operation -> JsString(-), expression1 -> JsNumber(10), expression2 -> JsNumber(2))), expression2 -> JsObject(Map(operation -> JsString(+), expression1 -> JsNumber(1), expression2 -> JsNumber(2)))))
scala> val jsonString = Json.stringify(json)
jsonString: String = { op: "+", expr1: { op: "-", expr1: 10, expr2: 2 }, expr2: { op: "+", expr1: 1, expr2: 2 } }
trait JsonConverter[A] {
def convert(a: A): JsValue
}
object Json {
def stringify(jsValue: JsValue): String = // as before
def toJson[A](a: A, jsonConverter: JsonConverter[A]): JsValue = jsonConverter convert a
}
object expressionJsonConverter extends JsonConverter[Expression] {
override def convert(a: Expression): JsValue = a match {
case Value(value) ⇒ JsNumber(value)
case Add(e1, e2) ⇒ JsObject {
Map(
"op" → JsString("+"),
"expr1" → convert(e1),
"expr2" → convert(e2)
)
}
case Subtract(e1, e2) ⇒ JsObject {
Map(
"op" → JsString("-"),
"expr1" → convert(e1),
"expr2" → convert(e2)
)
}
}
}
scala> val json = Json.toJson(expression, expressionJsonConverter)
json: JsValue = JsObject(Map(operation -> JsString(+), expression1 -> JsObject(Map(operation -> JsString(-), expression1 -> JsNumber(10), expression2 -> JsNumber(2))), expression2 -> JsObject(Map(operation -> JsString(+), expression1 -> JsNumber(1), expression2 -> JsNumber(2)))))
scala> val jsonString = Json.stringify(json)
jsonString: String = { op: "+", expr1: { op: "-", expr1: 10, expr2: 2 }, expr2: { op: "+", expr1: 1, expr2: 2 } }
We need just to make a few modifications to promote JsonConverter
into a typeclass
@implicitNotFound("Please define an implicit JsonConverter[${A}]")
trait JsonConverter[-A] {
def convert(a: A): JsValue
}
object JsonConverter {
def apply[T: JsonConverter]: JsonConverter[T] = implicitly[JsonConverter[T]]
}
object Json {
def stringify(jsValue: JsValue): String = // as before
def toJson[A: JsonConverter](a: A): JsValue = JsonConverter[A] convert a
}
scala> implicit val conv = expressionJsonConverter
conv: expressionJsonConverter.type = expressionJsonConverter$@4fb81683
scala> val json = Json.toJson(expression)
json: JsValue = JsObject(Map(operation -> JsString(+), expression1 -> JsObject(Map(operation -> JsString(-), expression1 -> JsNumber(10), expression2 -> JsNumber(2))), expression2 -> JsObject(Map(operation -> JsString(+), expression1 -> JsNumber(1), expression2 -> JsNumber(2)))))
scala> val jsonString = Json.stringify(json)
jsonString: String = { op: "+", expr1: { op: "-", expr1: 10, expr2: 2 }, expr2: { op: "+", expr1: 1, expr2: 2 } }
sealed trait Expression[A]
type IntE = Expression[Int]
case class IntValue(value: Int) extends IntE
case class Add[E1 <: IntE, E2 <: IntE](expr1: E1, expr2: E2)
extends IntE
case class Subtract[E1 <: IntE, E2 <: IntE](expr1: E1, expr2: E2)
extends IntE
type BoolE = Expression[Boolean]
case class BooleanValue(value: Boolean) extends BoolE
case class And[E1 <: BoolE, E2 <: BoolE](expr1: E1, expr2: E2)
extends BoolE
case class Or[E1 <: BoolE, E2 <: BoolE](expr1: E1, expr2: E2)
extends BoolE
case class Not[E <: BoolE](expression: E) extends BoolE
case class LessThan[E1 <: IntE, E2 <: IntE](expr1: E1, expr2: E2)
extends BoolE
case class GreaterThan[E1 <: IntE, E2 <: IntE](expr1: E1, expr2: E2)
extends BoolE
case class If[P <: BoolE, B1 <: IntE, B2 <: IntE](pred: P,
branch1: B1,
branch2: B2)
extends IntE
@implicitNotFound("Please define an implicit JsWrite[${A}]")
trait JsWrite[A] {
def write(a: A): JsValue
}
object JsWrite {
def apply[T: JsWrite]: JsWrite[T] = implicitly[JsWrite[T]]
}
object Json {
def stringify(jsValue: JsValue): String = // as before
def toJson[A: JsWrite](a: A): JsValue = JsWrite[A] write a
}
object JsonWriters {
implicit val jsWriteIntValue = new JsWrite[IntValue] {
override def write(intValue: IntValue): JsValue =
JsNumber(intValue.value)
}
implicit def jsWriteAdd[E1 <: IntE : JsWrite, E2 <: IntE : JsWrite] =
new JsWrite[Add[E1, E2]] {
override def write(add: Add[E1, E2]): JsValue = JsObject(Map(
"op" → JsString("+"),
"expr1" → (JsWrite[E1] write add.expr1),
"expr2" → (JsWrite[E2] write add.expr2)))
}
// jsWriteSubtract is similar to jsWriteAdd
}
object JsonWriters {
implicit val jsWriteBooleanValue = new JsWrite[BooleanValue] {
override def write(booleanValue: BooleanValue): JsValue =
JsBoolean(booleanValue.value)
}
implicit def jsWriteAnd[E1 <: BoolE : JsWrite, E2 <: BoolE : JsWrite] =
new JsWrite[And[E1, E2]] {
override def write(and: And[E1, E2]): JsValue = JsObject(Map(
"op" → JsString("&"),
"expr1" → (JsWrite[E1] write and.expr1),
"expr2" → (JsWrite[E2] write and.expr2)))
}
// jsWriteOr and jsWriteNot are similar to jsWriteAnd
}
object JsonWriters {
implicit def jsWriteLessThan[E1 <: IntE : JsWrite, E2 <: IntE : JsWrite] =
new JsWrite[LessThan[E1, E2]] {
override def write(lessThan: LessThan[E1, E2]): JsValue = JsObject(Map(
"op" → JsString("<"),
"expr1" → (JsWrite[E1] write lessThan.expr1),
"expr2" → (JsWrite[E2] write lessThan.expr2)))
}
// jsWriteGreaterThan is similar to jsWriteLessThan
implicit def jsWrIf[P<:BoolE : JsWrite, B1<:IntE : JsWrite, B2<:IntE : JsWrite] =
new JsWrite[If[P, B1, B2]] {
override def write(`if`: If[P, B1, B2]): JsValue = JsObject(Map(
"op" → JsString("if"),
"pred" → (JsWrite[P] write `if`.pred),
"branch1" → (JsWrite[B1] write `if`.branch1),
"branch2" → (JsWrite[B2] write `if`.branch2)))
}
}
@implicitNotFound("Please define an implicit Eval[${A}, ${B}]")
trait Eval[A, B] {
def eval(a: A): B
}
object Eval {
def evaluate[A, B](a: A)(implicit ev: Eval[A, B]): B = ev eval a
}
object Evaluators {
implicit val evalIntValue = new Eval[IntValue, Int] {
override def eval(intValue: IntValue): Int = intValue.value
}
implicit def evalAdd[E1 <: IntE, E2 <: IntE](implicit evE1: Eval[E1, Int],
evE2: Eval[E2, Int]) =
new Eval[Add[E1, E2], Int] {
override def eval(add: Add[E1, E2]): Int =
(evE1 eval add.expr1) + (evE2 eval add.expr2)
}
// evalSubtract is similar to evalAdd
}
object Evaluators {
implicit val evalBooleanValue = new Eval[BooleanValue, Boolean] {
override def eval(booleanValue: BooleanValue): Boolean = booleanValue.value
}
implicit def evalAnd[E1 <: BoolE, E2 <: BoolE](implicit evE1: Eval[E1, Boolean],
evE2: Eval[E2, Boolean]) =
new Eval[And[E1, E2], Boolean] {
override def eval(and: And[E1, E2]): Boolean =
(evE1 eval and.expr1) && (evE2 eval and.expr2)
}
// evalOr and evalNot are similar to evalAnd
}
object Evaluators {
implicit def evalLessThan[E1 <: IntE, E2 <: IntE](implicit evE1: Eval[E1, Int],
evE2: Eval[E2, Int]) =
new Eval[LessThan[E1, E2], Boolean] {
override def eval(lessThan: LessThan[E1, E2]): Boolean =
(evE1 eval lessThan.expr1) < (evE2 eval lessThan.expr2)
}
// evalGreaterThan is similar to evalLessThan
implicit def evIf[P<:BoolE, B1<:IntE, B2<:IntE](implicit evP: Eval[P, Boolean],
evB1: Eval[B1, Int],
evB2: Eval[B2, Int]) =
new Eval[If[P, B1, B2], Int] {
override def eval(`if`: If[P, B1, B2]): Int =
if (evP eval `if`.pred) evB1 eval `if`.branch1
else evB2 eval `if`.branch2
}
}
scala> val expression =
| If(
| And(
| LessThan( Add( Add( IntValue(2), IntValue(3) ), IntValue(4) ), IntValue(23) ),
| GreaterThan( IntValue(45), IntValue(12) )
| ),
| Add( IntValue(2), IntValue(2) ),
| IntValue(5)
| )
expression: If[And[LessThan[Add[Add[IntValue,IntValue],IntValue],IntValue],GreaterThan[IntValue,IntValue]],Add[IntValue,IntValue],IntValue] = If(And(LessThan(Add(Add(IntValue(2),IntValue(3)),IntValue(4)),IntValue(23)),GreaterThan(IntValue(45),IntValue(12))),Add(IntValue(2),IntValue(2)),IntValue(5))
scala> import JsonWriters._; import Evaluators._
scala> val json = Json.toJson(expression)
json: JsValue = JsObject(Map(op -> JsString(if), pred -> JsObject(Map(op -> JsString(&), expr1 -> JsObject(Map(op -> JsString(<), expr1 -> JsObject(Map(op -> JsString(+), expr1 -> JsObject(Map(op -> JsString(+), expr1 -> JsNumber(2), expr2 -> JsNumber(3))), expr2 -> JsNumber(4))), expr2 -> JsNumber(23))), expr2 -> JsObject(Map(op -> JsString(>), expr1 -> JsNumber(45), expr2 -> JsNumber(12))))), branch1 -> JsObject(Map(op -> JsString(+), expr1 -> JsNumber(2), expr2 -> JsNumber(2))), branch2 -> JsNumber(5)))
scala> val jsonString = Json.stringify(json)
jsonString: String = {op: "if", pred: {op: "&", expr1: {op: "<", expr1: {op: "+", expr1: {op: "+", expr1: 2, expr2: 3}, expr2: 4}, expr2: 23}, expr2: {op: ">", expr1: 45, expr2: 12}}, branch1: {op: "+", expr1: 2, expr2: 2}, branch2: 5}
scala> val result = Eval.evaluate(expression)
result: Int = 4