Hypothesis #1

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...

Hypothesis #2 — 1/2

Define some custom type A

scala> case class MyClass(x: Int)
defined class MyClass

Hypothesis #2 — 2/2

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!

Source to the rescue!

sorted method defined in SeqLike[+A, +Repr]

def sorted[B >: A](implicit ord: Ordering[B]): Repr

Note:

• sorted does take a parameter, which can be implicitly provided
• some polymorphic relationship between B and Ordering[B]

Quick detour on implicits

implicit is a keyword

Types:

• conversions
• parameters

implicit conversions

Two subtypes:

Conversion to an expected type

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!

Conversion of the receiver (enrich-my-library pattern)

implicit class Person(val name: String) {
  def greetMe: String = s"""Hello $name!"""
}

scala> "Julien".greetMe
res0: String = Hello Julien!

implicit parameters

def add(a1: Int)(implicit a2: Int) = a1 + a2
implicit val one: Int = 1

scala> add(22)
res0: Int = 23

Back to the investigation

Ordering[T] definition:

@annotation.implicitNotFound(msg = "No implicit Ordering defined for ${T}.")
trait Ordering[T] extends Comparator[T] with PartialOrdering[T]
  with Serializable {
  // implementation
}

Note:

• Ordering[T] extends java.util.Comparator[T]
• @implicitNotFound is what is generating the error message we saw earlier

Nuts & bolts

• Ordering[Int] argument was implicitly provided
• Ordering[Int] is used by sorted to sort Int elements
• If we can provide an Ordering[A] we can sort any List[A]

Time to sort our list! — 1/2

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!

Time to sort our list! — 2/2

...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!

Source to the rescue! — 1/2

Definition of sum in TraversableOnce[+A]

def sum[B >: A](implicit num: Numeric[B]): B = foldLeft(num.zero)(num.plus)

Looks familiar, uh?

Source to the rescue! — 2/2

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

Don't panic!

An implicitly available CanBuildFrom[Repr, B, That]?

Could that be a more sophisticated variation of what we have just seen?

Source to the rescue again! — 1/2

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

Source to the rescue again! — 2/2

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
}

How it works — 1/2

When invoking map there has to be an implicit CanBuildFrom[Repr, B, That], where:

1. Repr is inferred as List[MyClass]
2. type B is inferred as String

How it works — 2/2

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...
}

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

Definition, revised

I found Daniel Westheide's explanation on his The Neophyte's Guide to Scala much more readable

A type class TC defines some behaviour in the form of operations that must be supported by a type A for it to be a member of type class TC. Whether the type A is a member of the type class TC 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, once A is made a member of the type class TC, functions that have constrained one or more of their parameters to be members of TC can be called with arguments of type A.

Scala's typeclasses machinery

To carve and use your own typeclass in Scala you need to define:

1. Some behaviour defined in a trait, parametrised on one or more types
2. An instance of this trait for some type A, which the compiler can find in the implicit scope

That's it. Nothing more, really.

Nice to haves

I'd recommend you doing:

• Always stick the @implicitNotFound annotation on the definition of your typeclass and provide a self-explanatory error message
• If you can provide some implicits out of the box, put them into the companion object of your typeclass
• Use the context bound syntax, where applicable
• 

  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]] }

Def on singleton w/ recursive calls — Definition site

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

Def on singleton w/ recursive calls — Call site

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

A JSON ADT — Definition site — 1/2

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("{ ", ", ", " }")
}

A JSON ADT — Definition site — 2/2

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)
      )
    }
  }
}

A JSON ADT — Call site

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 } }

The Adapter Pattern (GoF) for JSON — Definition site

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)
      )
    }
  }
}

The Adapter Pattern (GoF) for JSON — Call site

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 } }

The JsonConverter typeclass — Definition site

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
}

The JsonConverter typeclass — Call site

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 } }

A more complex ADT — 2/3

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

A more complex ADT — 3/3

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

JsonConverter renamed & revised

@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
}

JsWriters — 1/3

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
}

JsWriters — 2/3

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
}

JsWriters — 3/3

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)))
    }
}

Typeclass for Eval!

@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
}

Evaluators — 1/3

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 
}

Evaluators — 2/3

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
}

Evaluators — 3/3

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
    }
}

Call site

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