Implicits, type classes, and extension methods

Implicits. For some people, they are an indispensable feature of Scala, that allows achieving otherwise impossible things. For others a sole reason to avoid using the language. As far as I can tell the majority of the later never really learned how to use them right.

Implicit val, def, conversion, class…

First of all, implicit is not a thing. There are several distinct ideas, all of which use the same keyword implicit, using the same internal mechanism, but in the end, doing different things for different reasons. We could group them like this:

• implicit parameter,
• implicit val and implicit def taking only implicit parameters,
• implicit def taking one parameter - implicit conversion,
• implicit class.

However, this division tells us nothing. I think, in order to understand implicits it’s best to talk about them using concrete use cases, and only then look at what they have in common.

Type-based Dependency Injection

Let’s start with a simple case.

def runServer(config: Config, ec: ExecutionContext): Unit 
def runMigrations(config: Config, ec: ExecutionContext): Unit
def runREPL(config: Config, ec: ExecutionContext): Unit

// config.mode is an enum telling which run mode user wanted
def startApp(config: Config, ec: ExecutionContext): Unit =
config.mode match {
  case Server => runServer(config, ec)
  case Migrations => runMigrations(config, ec)
  case REPL => runREPL(config, ec)
}

val config: Config
val ec: ExecutionContext

startApp(config, ec)

As we can see, here we simply pass dependencies around. Additionally, these dependencies have unique types. In this scope we could find only one instance for each type we would ask compiler about. So, we can imagine, we could ask the compiler to do something like:

def startApp(use here the only thing of type Config,
             use here the only thing of type: ExecutionContext): Unit =
(that only Config thing).mode match {
  case Server => runServer(pass Config for me, pass ExecutionContext for me)
  case Migrations => runMigrations(pass Config for me, pass ExecutionContext for me)
  case REPL => runREPL(pass Config for me, pass ExecutionContext for me)
}

startApp(pass Config for me, pass ExecutionContext for me)

Of course, this would break pretty easily. Put another Config and ExecutionContext here and the compiler would not be able to guess, which object we want. So, let’s mark them:

mark as special val config: Config
mark as special val ec: ExecutionContext

This too would fail if we marked 2 Configs or ExecutionContexts as special, but at least this would be a thing we could do something about.

At this point, we can notice, that since it’s the compiler that passes objects for us, we don’t have to write them ourselves:

startApp

The compiler knows, that it needs here one Config and one ExecutionContext, and in order to find them it searches through the list of objects marked as special. Then all we would see is that these parameters were passed implicitly.

This is the reason, why implicit is the keyword we use to mark the variables. It is also the keyword used to mark the parameter list which arguments should be filled by values from implicit scope:

def runServer(implicit config: Config, ec: ExecutionContext): Unit 
def runMigrations(implicit config: Config, ec: ExecutionContext): Unit
def runREPL(implicit config: Config, ec: ExecutionContext): Unit

def startApp(implicit config: Config, ec: ExecutionContext): Unit =
config.mode match {
  case Server => runServer
  case Migrations => runMigrations
  case REPL => runREPL
}

implicit val config: Config
implicit val ec: ExecutionContext

startApp

There are some rules regarding implicits:

• implicits cannot be ambiguous. You cannot define 2 implicits with the same type in the same scope,
• however, class and its subclass are slightly different scopes. The rule of thumb is that in such cases, the closer scope would win. However, as always it is a bit more complex, so we will explain that later on,
• companion objects are also checked for implicits. If you have type X, then X companion will be checked for X implicits, but also for F[X] or X[A] (this will be explained later, as we reach type classes),
• a method can have one parameter list, which will be marked as implicit. As of now, it will always be the last parameter list. Each of params will become implicit value (so you cannot get params from the implicit scope, but not make them implicits themselves).

For convenience scala.Predef defines utility, that allows us to get implicit by its type:

@inline def implicitly[T](implicit e: T) = e

implicit val s: String = "test"

implicity[String] // "test"

Most of the time, these rules work quite good. There is at least one case though, where they can break your code unexpectedly:

implicitly[X] // gets correct X from some other scope

class Y {
  
  implicit val x: X = implicitly[X]
}

(new Y).x // null!

If you run this particular code, you could be surprised, why y.x would return null. Problem is, that usually when we define variables, they become available only from the moment they are defined. However, class parameters are always accessible from any place in the class - even before they are initialized. Normally, scalac would produce an error if you explicitly tried to access uninitialized val. However, here it is not so obvious - value comes from implicitly[X]. Unfortunately, implicitly takes it from the closest scope it can find - which is Y class - at this point, not initialized completely.

I think I stumbled on this issue only twice. But the first time it was a nightmare, to figure out what was happening. It only shows how complex things can get once several features are used at once.

Instance produced on demand

Notice, that implicit instances so far were defined as values. We had to define a complete type and implementation. But, let’s say we want to always have an instance of a List that is an empty List. The List has a type parameter. What now?

implicit def emptyList[T]: List[T] = List.empty[T]

implicitly[List[String]] // Nil
implicitly[List[Int]] // Nil

That wasn’t very interesting. But let’s say we want a Stream, and we want it to be filled with a value of implicit scope. Can we do it?

implicit s: String = "test"
implicit i: Int = 0

implicit def streamOfT[T](implicit value: T): Stream[T] =
  Stream.continually(value)

implicitly[Stream[String]] // Stream("test", "test", ...)
implicitly[Stream[Int]] // Stream(0, 0, ...)

We see, that we can use implicit def to define value in scope in a more dynamic way. It can even be fed with other values from implicit scope! But now one would write a code like that in examples: passing around primitives is not a not going to work in a long run. So, what is the actual benefit of this mechanism and what is the reason for implicits’ existence in the first place?

Flavors of polymorphism

It all begins with Haskell and polymorphism. Both mathematicians and programmers want to reuse concepts that they already spent time inventing. In order to do so, they need a way to generalize where possible, only specializing where needed. Polymorphism is a general idea, about having different kinds of data, that have something in common, which allows you to perform same operations on them. In object-oriented programming, that usually is related to sharing a common interface, but that’s just one case. Actually, there are 3 different kinds of polymorphism:

• Subtyping aka subtype polymorphism. Within one type, you have a subset of values making another type. OO languages usually implement it with interface inheritance. Because the subtype must fulfill all requirements and assertions of the supertype, the supertype can be treated as a generalization and common denominator of all its subtypes.

  (That is the ideal situation - OO programmers need to be actively reminded about Liskov substitution principle. A lot of bugs were born when someone overrode a method and created a class that shared an interface with the superclass but couldn’t be used as a drop-in replacement).

• Parametric polymorphism, List of Strings should behave the same as List of Ints. So why not let them have the same implementation? Of course, they have to have different types, so that we don’t put integers into a list of strings and vice versa. Type parameters let us define a whole implementation where instead of a type we put a placeholder, and when we supplement it with a concrete type, the implementation is materialized.

  There is also another way to look at it - mathematical one. Functions, in general, are sets of arguments-values pairs. Types are also sets of values. And set might be both an argument and a value of a function. So it is possible to create a function taking a type as an argument and returning another type as a value. An example of such function (called type constructor) would be List[_], which takes a parameter e.g. String and then returns a concrete type e.g. List[String].

• Ad-hoc polymorphism aka operator overloading. You have * (or +) operator and you want to be able to use if for multiplying: ints, longs, doubles, floats, complex numbers, vectors, matrices… For each type it would have a slightly different implementation, so you cannot just create one function that rules them all, and simply adjust the type (as is the case with parametric polymorphism), nor extract common behavior (what matrices multiplication has in common with multiplying scalars?).

  As a matter of the fact, each overloaded function is actually a set of different functions, sharing the same name, where one that will be used is based on a type of the argument(s) (and their number aka arity).

The distinction between all 3 kinds of polymorphism is very important. At some point, developers of Haskell needed to introduce some kind of polymorphism to handle things like mentioned multiplication or addition, but not by having everything being build into the language. They wanted their polymorphic solution to be extensible. Parametric polymorphism is not a solution to this problem and they didn’t want to introduce subtyping with its shares of problems with inheritance.

Type classes in Haskell

The solution originally described in the paper How to make ad-hoc polymorphism less ad hoc works as follows:

• let us define a named contract. This contract would require, that for a type certain functions have to be defined and meet certain assertions,
• when type declared itself as following the said contract, then somewhere in the scope of program required functions have to be defined and explicitly pointed to (and have to follow assertions),
• operators like *, + etc have assigned contracts, and are used as syntactic sugar for functions mentioned in their contracts,
• one contract can inherit obligations from another contract and add to them.

Such contracts would be named type classes. Let us see this idea by the example of a monoid.

A monoid is an algebra of elements that could be combined together.

We could define it formally as a triple $(A, \oplus, 0)$, where:

• we would require $\oplus$ to be binary operator over $A$:

• which is also associative:

• and has a neutral element $0$:

Examples of such monoids would be: numbers with addition and 0, numbers with multiplication and 1, lists of the same type with list concatenation and an empty list, matrices of the same size with matrix addition with a matrix of zeros, square matrices of the same size with matrix multiplication and an identity matrix.

Haskell would define such contract this way:

class Monoid m where
  mempty :: m            -- neutral element
  mappend :: m -> m -> m -- operator A x A -> A
  mconcat :: [m] -> m    -- fold list (e.g. calc sum/product)
  -- defining mconcat is optional, since it has the following default:
  mconcat = foldr mappend mempty
 
-- this infix synonym for mappend is found in Data.Monoid
x <> y = mappend x y
infixr 6 <>

together with the following laws:

-- Identity laws
x <> mempty = x
mempty <> x = x
 
-- Associativity
(x <> y) <> z = x <> (y <> z)

An implementation for numbers would look like:

newtype Sum n = Sum n
 
instance Num n => Monoid (Sum n) where
  mempty = Sum 0
  mappend (Sum x) (Sum y) = Sum (x + y)
  
newtype Product n = Product n
 
instance Num n => Monoid (Product n) where
  mempty = Product 1
  mappend (Product x) (Product y) = Product (x * y)

(Examples are taken from Haskell wiki).

While this syntax might be alien to quite a lot of people, it should show us a few things:

• Haskell uses names that no other language would consider newcomer friendly (mempty - monoid-empty, mappend - monoid-append, mconcat - monoid-concatenate),
• Haskell kind of wraps types in Sum or Product, because both addition and multiplication are monoids and it has to distinct them somehow which one we want to use,
• Haskell borrowed class and instance keywords from object-oriented languages,
• if we think about it… it is not about declaring a class at all! That is unless we assume that Haskell only lets us use class to define parametrized trait with an interface and assertions, while instance only allow us to create one global singleton instance of the interface per type used as a parameter.

Considering that a type class is not really a class, but has class in its name it is not surprising that people are confused about them! But let’s get back to Scala.

Type classes in Scala

Odersky found an idea of type classes appealing and wanted to have them in Scala. There were some issues though:

• JVM basically won’t let you make sure that several functions are defined at once in other way than by putting them into the same interface,
• Haskell would supply the right implementation inside parametrized type and each parametrized function is turned into a specialized version, which might have all occurrences of an overload function replaced with a pointer to a specific implementation,
• also Haskell can look through the whole scope for an implementation for a specific type. With JVM ecosystem where you compile stuff directly to the bytecode and later on you would have trouble re-compiling stuff because new type appeared. @Specialize won’t help either, since it only generates special cases for primitives.

To address the issues, he chooses following solutions:

• type classes with be implemented as actual classes. Or trait. This way you will have to guarantee,
• wherever you use a type class, you will call a method on an actual instance which will store all necessary information about types inside,
• the fact that you call this code from type-erased generic implementation that could have been compiler somewhere else won’t be an issue, because you will use dependency injection to get it.

So you could implement type classes this way:

trait Monoid[A] {
  def empty: A
  def append(a1: A, a2: A): A
  def concat(list: List[A]): A = list.foldRight(empty)(append)
}

val intMonoid = new Monoid[Int] {
  def empty: Int = 0
  def append(a1: Int, a2: Int): Int = a1 + a2
}

def combineValues[T](
  map: Map[String, List[T]]
)(monoid: Monoid[T]): Map[String, T] =
  map.mapValues(monoid.concat)

combineValues(Map(
  "test1" -> List(1, 2, 3, 4, 5),
  "test2" -> List(6, 7, 8, 9, 0)
))(intMonoid)

Thing is, usually, you want to have only one type class for each type in the scope. Additionally, such usage would introduce clumsiness the original solution hasn’t. Therefore the idea of implicits was born. Originally, implicits were introduced as a way of automatically passing type classes where needed basing solely on their type.

object Monoid {
  
  implicit val intMonoid: Monoid[Int] = new Monoid[Int] {
    def empty: Int = 0
    def append(a1: Int, a2: Int): Int = a1 + a2
  }
}

def combineValues[T](
  map: Map[String, List[T]]
)(implicit monoid: Monoid[T]): Map[String, T] =
  map.mapValues(monoid.concat)

combineValues(Map(
  "test1" -> List(1, 2, 3, 4, 5),
  "test2" -> List(6, 7, 8, 9, 0)
))

Here we can notice one interesting thing about type classes and implicits: when you need an implicit of type F[A] compiler will look for it inside companion objects of F and A if no implicit could be found in the current scope. This way, you don’t have to define/import them everywhere if you just want to rely on default.

But passing type classes could be made simpler even further. Since the most common use case is a type class with one parameter, you can declare them as context bounds.

def needMonoid[T](ts: List[T])(implicit monoid: Monoid[T]): T =
  monoid.concat(ts)
// could be written with context bound
def needMonoid[T: Monoid](ts: List[T]): T =
  implicitly[Monoid[T]].concat(ts)

def severalBoundArePossible[T : Bound1 : Bound2]: Unit = {
  implicitly[Bound1[T]]
  implicitly[Bound2[T]]
}

With context bound notation you declare that you need an implicit. It will become available in implicit scope, but it has no name you can use. This is why:

• it won’t cause unused parameter issue if you just want to force some contract, but not made use of if (e.g. implicit evidence),
• you can pass it inside a method to another method that requires it,
• if you want to use it, you need to extract it from implicit scope manually e.g. with implicitly[T].

In type-class-heavy libraries like e.g. Cats you can see an interesting pattern to avoid using the whole implicitly[Typeclass[T]]:

object Monoid {
  
  def apply[T: Monoid]: Monoid[T] = implicitly[Monoid[T]]
  def append[A: Monoid]:(a1: A, a2: A): A = apply[A].append(a1, a2)
  def concat[A: Monoid](list: List[A]) = apply[A].concat(list)
}

Once you define such helpers inside a companion, you can use them inside a code making the context very clear:

def combineValues[T: Monoid](map: Map[String, List[T]]): Map[String, T] =
  map.mapValues(Monoid.concat[T])

If you’ll ever start working with really FP-heavy libraries like Cats or Scalaz, you’ll notice that concepts everywhere.

Type class derivation

Type classes are surely useful, but they wouldn’t as nearly useful as they are if not for the ability to create a new type class basing on existing instances and rules of how to compose them together automatically.

For instance:

trait Show[T] {
  
  def show(value: T): String
}

object Show {
  
  def apply[T: Show]: Show[T] = implicitly[Show[T]]
  def show[T: Show](value: T): String = apply[T].show(value)
  
  implicit val showString: Show[String] = s => s
  implicit val showInt: Show[Int] = _.toString
  
  implicit def showTuple[T: Show, U: Show]: Show[(T, U)] =
    tuple => s"(${Show.show[T](tuple._1)}, ${Show.show[U](tuple._2)})"
}

Show.show(12 -> "34") // "(12, 34)"

Deriving type classes like that would be quite limiting, while is where Shapeless comes in. It allows us to represent many classes (surely all algebraic data types that Scala supports: products and coproducts) in a generic form, which we can inductively iterate and build the final type class step-by-step. Usually, the process works like this:

• find a generic representation for a type (heterogeneous list for products, coproduct for sum types) (1),
• for generic representation try to find an implicit for the head, and implicit for the tail (2),
• support recursion stop condition (empty HList/Coproduct) (3),
• use a Generic to adjust code working on generic representation for your specific representation.

import shapeless._

object Show {
  
  ... // instances for the "primitives" we would build upon
  
  // (1)
  implicit def showProduct[S, T <: HList](implicit gen: Generic.Aux[S, T],
                                          show: Show[T]): Show[S] =
  s => {
    // (4)
    val hlist: T = gen.to(s) // our concrete S to hlist T translation!
    val result = show.show(hlist)
    // in some cases here we also get result basing
    // on generic representation and we have to convert it back.
    // it is not the case here, but might be in genreal
    result.substring(0, result.length - 2) // drop ", "
  }
  
  // (2)
  implicit def showCons[H: Show, T <: HList: Show]: Show[H :: T] =
    cons => Show[H].show(cons.head) + ", " + Show[T].show(cons.tail)
  
  // (3)
  implicit val showHNil: Show[HNil] = _ => ""
}

case class MyNewType(str: String, int: Int)

Show.show[MyNewType](NuNewType("test", 10)) // "test, 10"

Why do we need shapeless?

Let’s be clear: I don’t intend to provide a full lecture on shapeless here. There is already an excellent (and free) book about it named The type astronaut’s guide to shapeless. I only want to describe a general idea to encourage you to read it.

If we try to describe data mathematically we might find out that we will have to deal with one of 3 cases:

• our data type is a primitive of a sort. We cannot (or don’t want to) split it into smaller parts,
• it is a container of a sort. It might be a container of some number of elements of the same type (like lists or sets). It might be a container, where elements might have different type and we tell them apart from their position (tuples) or a name/label associated with them (a record/class attribute/field). We can describe them all as different variants of a Cartesian product. When it comes to types we call them product types,
• our type is an alternative of 2 or more other types. Though each of them could exist in a separation, we also want to be able to tell: T is one of X, Y, Z. Mathematically, the set of such type’s values is a sum of sets of values of each of the component types. Because of that, they are called sum types, or (as a complement to product types) coproducts. When we use this concept in the context of a category theory and FP, we would put an additional add constraint: sets of values of each component type must be disjoint so that you could tell unambiguously to which subset your value belongs. Because of that we also call them disjoint unions.

Products and coproducts together form algebraic data types (ADTs).

If we wanted to use such knowledge to get a type class, the first case is easy. How, about other two?

case class A(s: String, i: Int)
case class B(x: String, y: Int)
type C = (String, Int)

We can see here, that all of the types are in a way one and the same: various implementations of the same Cartesian product $String \times Int$. As such, we could conclude, that whatever mechanisms we have for them could be shared (that is, as long as labels don’t matter).

A way of handling it is by providing some common representation. If possible, it should be one that could be inductively built. As a matter of the fact, there is such generic representation for a product type called heterogeneous list (HList).

sealed trait HList

// empty HList
sealed trait HNil extends HList {
  
  def ::[H](head: H): H :: HNil = ::(head, HNil)
}
case object HNil

// prepend element
final case class ::[H, T <: HList](head: H, tail: T) extends HList

"test" :: 10 :: HNil // String :: Int :: HNil

If we obtain such representation it is easy, to build up a type class for a whole generic representation one implicit at a time.

object Show {
  
  ...
  
  implicit def showCons[H: Show, T <: HList: Show]: Show[H :: T] =
    cons => Show[H].show(cons.head) + ", " + Show[T].show(cons.tail)
  
  implicit val showHNil: Show[HNil] = _ => ""
}

The most problematic thing would be: how to translate to generic and back? This is exactly the reason why shapeless was made: to provide such standard implementation as well as a mechanism to handle the translation. This mechanism is Generics.

object Show {
  
  ..
  
  implicit def showProduct[S, T <: HList](implicit gen: Generic.Aux[S, T],
                                          show: Show[T]): Show[S] =
  s => {
    val hlist: T = gen.to(s)
    val result = show.show(hlist)
    result.substring(0, result.length - 2) // drop ", "
  }
}

An instance of a Generic will be generated automatically by shapeless (which underneath uses macros to create them) for cases where it is possible (simplifying: as long as you use sealed traits for sum types and case classes for product types, you are good to go).

Each Generic has 2 methods: to taking the specific representation and translating it to generic representation and from which translates to specific representation from generic one.

There is also a twin generic representations for coproducts, also handled by generics.

sealed trait Coproduct

sealed trait :+:[+H, +T <: Coproduct]

// value is the "left" element of the sum (head)
case class Inl[+H, +T <: Coproduct](head : H) extends :+:[H, T]

// value is one of types in the tail
case class Inr[+H, +T <: Coproduct](tail : T) extends :+:[H, T]

// exists only for the sake of pattern matching and implementation simplicity
sealed trait CNil extends Coproduct

object Show {
  
  ...
  
  implicit def showCons[H: Show, T <: Coproduct: Show]: Show[H :+: T] = {
    case Inl(head) => Show[H].show(head)
    case Inr(tail) => Show[T].show(tail)
    case CNil      => ""
  }
  
  implicit def showCoproduct[S, T <: Coproduct](implicit gen: Generic.Aux[S, T],
                                                show: Show[T]): Show[S] =
  s => {
    val coproduct: T = gen.to(s)
    show.show(coproduct)
  }
}

Notice, that there are no separate Generic types for HLists and Coproducts. What you’ll get depends only on type bounds you place on an implicit.

Implicit evidence and aux pattern

You might have noticed something interesting about the generic representation in the example above.

Generic.Aux[T, U]

The definition of a Generic in shapeless looks like this:

trait Generic[T] extends Serializable {
  /** The generic representation type for {T},
      which will be composed of {Coproduct} and {HList} types  */
  type Repr

  /** Convert an instance of the concrete type to the generic value
      representation */
  def to(t : T) : Repr

  /** Convert an instance of the generic representation to an instance of
      the concrete type */
  def from(r : Repr) : T
}

So, each Generic contains a type Repr with information what is the generic representation for a specific representation T. If we used path-dependent types we would refer to it as:

Generic[T]#Repr // or
gen.Repr

However, this would make the Repr virtually useless to us due to nature of path-dependent types. We could try to access it like:

Generic[T]#Repr =:= U

and then try to access the U. In such way, we would attempt to prove, that there is U type which is identical to Generic[T]#Repr. Such proof is named implicit evidence and if we don’t use it for anything else we usually name the variable ev.

import shapeless.=:!=

def changeType[A, B](list: List[A])(f: A => B)(implicit ev: A =:!= B): List[B] =
    list.map(f)

changeType(List(1,2,3,4))(_.toString)  // List("1", "2", "3", "4")

changeType(List(1,2,3,4))(_ * 2) // compilation fails

Scala provides us with 2 generalized type constraint and shapeless adds another one:

• =:= proves that 2 types are equal,
• <:< proves that one is strictly a supertype of another but not equal,
• <%< used to prove that one must be viewable as the other - it allows both upcasting as well as implicit conversion, which is a reason why it was deprecated and removed (we expand on this concept later on),
• =:!= proves that the types are not equal. This one is provided by shapeless.

Other useful proof is e.g. ClassTag. It proves that type has a Class[_] instance and provides it. It is not a general rule, but most of the proofs’ instances mentioned here are generated by the compiler when we ask for them.

In the context of Generic it means that what we try to achieve is to have 2 types, S and T, and we want to let the compiler figure out one of them and prove that they could be transformed to and from via a Generic instance.

Sadly, due to path dependent types and limitations of the Scala compiler, this would not work: the compiler will simply give up and won’t return any implicit proof.

However, we might trick it by representing the types in a way, where types don’t depend on each other:

object Generic {
  
  type Aux[T, Repr0] = Generic[T] { type Repr = Repr0 }
}

This trick which lets the compiler figure out the missing type and create a Generic representation for us is known as aux pattern. Aux means helper and indeed it is a type declaration used solely as a utility to help the compiler figure out the types.

Other shapeless utilities

You probably noticed, that Generic doesn’t give you any information about labels each field had originally, nor what was the original name of a type in a coproduct.

This is why next to generic there are also LabelledGenerics which encode the original label using Witnesses (a workaround for pre-2.13 Scala not having literal types).

sealed trait A
case class A1(int: Int) extends A
case class A2(str: String) extends A

def labelledH[S, T <: HList](
  get: S)(implicit gen: LabelledGeneric.Aux[S, T]) = gen.to(get)
def labelledC[S, T <: Coproduct](
  get: S)(implicit gen: LabelledGeneric.Aux[S, T]) = gen.to(get)

labelledH(A1(10))
// Int with labelled.KeyTag[Symbol with tag.Tagged[int], Int] :: HNil = 10 :: HNil

labelledC(A1(10): A)
// A1 with labelled.KeyTag[Symbol with tag.Tagged[A1], A1] :+:
//   A2 with labelled.KeyTag[Symbol with tag.Tagged[A2], A2] :+:
//   CNil = Inl(A1(10))

As a matter of the fact, LabelledGenerics are a mechanism which is used in libraries like Circe to automatically derive codecs for ADTs.

Implicit conversions

I mentioned implicit conversion next to <%< proof, which became deprecated long time ago. As a matter of the fact, for many people, implicit conversions are the reason to avoid implicits at all. What are they actually?

case class Wrapper(val int: Int) extends AnyVal

implicit def int2wrapper(int: Int): Wrapper = Wrapper(int)

def needWrapper(w: Wrapper): Unit = println(w)

needWrapper(34) // Wrapper(34) !

An implicit conversion (also known as view) is an implicit function (or method) which takes exactly one explicit parameter. It might have no other parameters or it might take all remaining parameters as implicits. But on both cases, it gives compiler enough information to replace one value of value returned by the implicit function call.

It was deprecated and deemed dangerous for exact the same reason why C++ developers make all single argument constructors explicit: most of the time it is called when you’d prefer a compiler error instead.

The most infamous implicit conversion I know is scala.Predef.any2stringadd. It might turn virtually Any object into any2stringadd, which adds + method and allows to concatenate objects like strings. Thing is, usually you want to add to number or collection, but if you messed you types you prefer to fail and know about it. any2stringadd will turn it into String concatenation, so the error you receive will be very far from the mistake you made.

Another issue with implicit conversions I learned is how collections work. Basically, Map is an example of a PartialFunction (you can can call apply and isDefinedAt on it), which in turn extends Function (which should be a total function - the perfect example that blindly following OOP actually hurts!). That means that if you made you map implicit, it will also be treated as an implicit conversion, so Scala will try to convert by key-value lookup.

So, is there any use case for implicit conversions? A reason why they were not removed completely?

Pimp-my-library pattern

Actually, there is. If we only want to create a decorator, which will perform one operation on an object, and then disappear (by either returning a result or an original object), then everything should be fine. Chances of things going wrong will drop even further if we make sure, that our decorator is not overly greedy when it comes to wrapping or when we must import conversion ourselves. (Implicit conversions themselves needs to be enabled either by import or by compiler flag).

class DoubleOps(val double: Double) extends AnyVal {
  
  isZero: Boolean = double == 0
}

implicit def doubleOps(double: Double): DoubleOps = new DoubleOps(double)

This way we are extending the original object with some additional methods, without modifying the original class. Such methods are called extension methods, classes that provide them usually have ExtensionMethods or Ops suffix, while the whole pattern is often referred to as pimp-my-library pattern.

The example above can be shortened using the implicit class syntax:

implicit class DoubleOps(val double: Double) extends AnyVal {
  
  isZero: Boolean = double == 0
}

Implicit classes have some limitations: they cannot be top-level objects, so we cannot put them outside a class/object/trait. If we want to use AnyVal we cannot put them in class/trait either. So, usually, you’ll end up putting them into an object or maybe package object.

This method addition is heavily used by both Cats and Scalaz. For instance for our Monoid and Show type classes:

implicit class MonoidSyntax[A](val a: A) extends AnyVal {
  
  def |+|(a2: A)(implicit monoid: Monoid[A]): A =
    monoid.append(a, a2)
}

implicit class ShowSyntax[A](val a: A) extends AnyVal {
  
  def show(implicit show: Show[A]): String = show.show(a)
}

def addAndShow[A: Monoid: Show](a1: A, a2: A): String =
  (a1 |+| a2).show

In such cases where extension methods are used to provide a consistent type-class-relates syntax, objects and classes that provide it are named, well, Syntax.

Typed Tagless Final Interpreter

If you looked at addAndShow[A: Monoid: Show] and started wonder if the whole program could be expressed like that, the answer is: yes, it’s known as typed tagless final interpreter.

import cats._, cats.syntax.all._
import io.circe._, io.circe.syntax._
import io.circe.generic.auto._
import io.circe.parser._
import monix.eval.Task, monix.execution.Scheduler.Implicits.global

final case class User(name: String, surname: String, email: String)

trait UserRepo {
  def fetchByEmail(email: String): Option[User]
  def save(user: User): Unit
}

class UserServices[F[_]: Monad](repo: UserRepo) {
  def parseJson(user: String): F[Option[User]] = Monad[F].unit.map(_ => decode[User](user).toOption)
  def asJson(user: User): F[String] = Monad[F].unit.map(_ => user.asJson.noSpaces)
  def fetchByEmail(email: String): F[Option[User]] = Monad[F].unit.map(_ => repo.fetchByEmail(email))
  def save(user: User): F[Unit] = Monad[F].unit.map(_ => repo.save(user))
}

class UserRepoInMemory extends UserRepo {
  private val users = scala.collection.mutable.Map.empty[String, User]
  def fetchByEmail(email: String): Option[User] = users.get(email)
  def save(user: User): Unit = users += (user.email -> user)
}

class Program[F[_]: Monad](userServices: UserServices[F]) {

  def store(json: String): F[Unit] = for {
    parsed <- userServices.parseJson(json)
    _ <- parsed.map(userServices.save).getOrElse(Monad[F].point(()))
  } yield ()

  def retrieve(email: String): F[String] = for {
    userOpt <- userServices.fetchByEmail(email)
    json <- userOpt.map(userServices.asJson _).getOrElse(Monad[F].point(Json.obj().noSpaces))
  } yield json
}

val userRepo: UserRepo = new UserRepoInMemory
val userServices = new UserServices[Task](userRepo)
val program = new Program[Task](userServices)

program.store("""{"name":"John","surname":"Smith","email":"john.smith@mail.com"}""").flatMap { _ =>
  program.retrieve("john.smith@mail.com")
}.runAsync.onComplete(println)

This is a variation of a showoff code I wrote one day. The original version also used some experimental library which defined implicits in companion objects and in the end run program twice: one time as Id (returning values immediately) and one time as Task executing it asynchronously.

In the name Typed Tagless Final Interpreter:

• interpreter refers to the fact that once we declare context bounds the operations will be run by something external (a type class). This something becomes an interpreter of the code defined by our methods,
• typed - at each point operations are typed and we don’t have to perform any sort of additional checking to ensure, that we are allowed to do what we do. Type classes provide allowed, typed set of operations, while extension methods let them we written down in a readable form,
• tagless - refers to the fact, that we can have more than one implementation, and we don’t need to decide which to use using tags we could pattern match on, neither in form of some value we compare, nor tagged union,
• final - refers to the fact, that we don’t operate on values when defining the interface interpreter would work on. If we used values directly and pattern match on it ourselves we would use the initial encoding, but if instead, we declare a set of functions that has to be implemented together (e.g. as a type class) - the final encoding. Then interpreter provides the implementation for these functions.

The goal of such architecture is decoupling the way you run your code (Try, Future, Task, IO, …) from the actual domain logic. Other solution for such problem (avoiding commitment to some monad early) are free monads, however, they create overhead to do the need of creating an intermediate representation which will be interpreted into the final computation. It is even possible to optimize TTFI.

Magnet pattern

Any list of interesting things we can do with implicits cannot be completed without magnet pattern. A magnet pattern is an alternative to method overload which might return different result types depending on input, where, instead of providing many method implementations, we provide one argument which decides the result type. This argument is called the magnet and it is created by an implicit conversion from some other type:

sealed trait Magnet {
  type Result
  
  def get(): Result
}

object Magnet {
  
  implicit def fromNullary[T](f: () => T)(implicit ec: ExecutionContext) =
    new Magnet {
      type Result = Future[T]
      def get() = Future { f() }
    }
  
  implicit def fromList[T](list: List[T]) =
    new Magnet {
      type Result = String
      def get() = list.mkString(", ")
    }
}

def withMagnet(magnet: Magnet): magnet.Result = magnet.get()

import scala.concurrent.ExecutionContext.Implicits.global
withMagnet(() => Set(1,2,3)) // Future(Set(1,2,3))

withMagnet(List(1,2,3)) // "1, 2, 3"

This is quite a powerful pattern, but not without its issues. If Magnet trait is not sealed it might be extended with new ways of implicitly converting argument into a Magnet. As such debugging errors becomes a real issue, as you have to guess why implicit conversion failed. Was it not imported? Was implicit ambiguous? Was some other implicit missing?

This pattern was popularized by Spray with blog post about its internal DSL, which also explains the rationale behind introducing it. It carried over to Akka HTTP, but I saw it also in other libraries e.g. sttp.

Functional dependencies

Magnet pattern is closely related to functional dependencies. In general, it states that some type parameters depends on other type parameters. Magnet pattern would be an example of functional dependencies, where result type of an operation depends on types of its operands (which are parametric).

It is more generic term than magnet pattern though. In Scala CanBuildFrom[From, Element, To] can, for instance, make sure that if you turn Map into Set, the Set will contain pairs.

Map(1 -> 2, 3 -> 4).to[List] 
// List[(Int, Int)] = List((1, 2), (3, 4))

In this case not only does returned type depends on the argument but - inside CanBuildFrom - types depend on one another. You can expect, that functional dependencies will appear in the context of implicit evidence and type classes.

Implicit resolution

To have a complete understanding of implicits we should understand how compiler decides what goes into the scope and which implicit should be used.

The high-level descriptions are the following:

• implicit is a mapping from type T to a value t: T,
• in order to find that value, Scala find all definitions in scope that might fit the definition, and then takes the most specific definition,
• if it cannot point to a single definition that is the most specific, a resolution fails as the implicit is ambiguous,
• if it has such definition which builds the value incrementally from other implicits and they are ambiguous, a resolution fails with divergent implicit expansion,
• of course, if there is not a single implicit that can match the definition then it is not found. This includes the situations when there is a definition for your type T, but it misses one definition for implicits required to build the value.

That begs 2 questions: that goes into the scope?, and what does it mean for a definition to be more specific?

Implicit scope

Scala will put into the implicit Scope the following definitions:

• implicit definitions defined in or passed into the current scope,
• implicit definitions defined is superclasses the current trait/class/object extends,
• implicit definitions imported to the current scope,
  • basically anything that you can access directly (without any prefix prefix.something)
• implicit definitions defined in companion objects or types related to the type $T$ you are resolving for:
  • if $T$ is compound type $T_1$ with … with $T_n$ then all implicits from all companions of $T_1$, …, $T_n$,
  • if $T$ is a parametrized type $S[T_1, ..., T_n]$ then implicits from all companions of $S$, $T_1$, … $T_n$,
  • if $T$ is a singleton type t.type then all implicits available for t,
  • if $T$ is a type projection $S$ # $U$ then all implicits available for $S$ and $T$,
  • if $T$ is a type alias then all implicits for its expansion,
  • if $T$ is an abstract type, all implicits for its upper bound,
  • if $T$ is about implicit conversion with arguments $T_1$, …, $T_n$ to type $U$ then all implicits from companions $T_1$, …, $T_n$ and $U$,
  • implicits for parts of quantified (existential or universal) and annotated types (e.g. T forSome { types }) are in implicit scope of $T$,
  • if course $T$ own companion.

As we can see compiler has a lot of implicits to consider for even remotely more complex type than a non-parametric type that extends nothing. As a rule of thumb we can assume, that if $U$ is somehow used in $T$’s definition, its companion object will be scanned.

Without these properties, type class derivation would be much more troublesome, but probably a lot faster.

Best definition

All right, we got a set of potentially tons of implicit definitions, and we have to decide on just one of them. How the compiler makes that decision? The same way it decides on overloading resolution - choosing the most specific alternative:

• for each 2 definitions $A$, $B$ calculate the relative weight:
  • if one is as specific as the other - weight 1 is is, 0 otherwise
  • if one is class/object being derived from the other class/object - weight 1 is is, 0 otherwise
  • sum the values
• if relative weight for $(A, B)$ is greater than $(B, A)$, then $A$ is more specific than $B$,
• if relative weight for $(A, B)$ is smaller than $(B, A)$, then $B$ is more specific than $A$.

Intuitively, for one definition to be as specific as the other, if you could replace one call with the other without issue with types (for more formal definition look at the specification).

For class $C$ to be derived from $D$, $C$ must be a subtype of $D$, or $C$/$D$ must be a companion object(s) of such classes that one extends the other (again, informal definition, take a look at the specification).

Considering that we use terms as specific as and more specific than, we are actually considering a subset of a partial order and then looking after the minimum of that subset (or maximum depending on how we define it). It makes sense as type hierarchy itself would also be a partial order.

Troublesome cases

Most of the time you’ll such definitions will result in pretty understandable behavior. There are some exceptions though.

What if you have 2 definitions, that are different, BUT could be used produce the same type? If their ranking decides that one is not more specific than th other, you’ll get an error (ambiguous implicit or diverging implicit expansion).

class A

class B[T]

object A {
  implicit val ai: B[A] = new B[A] { override def toString = "A" }
}

object B {
  implicit val bi: B[A] = new B[A] { override def toString = "B" }
}

implicitly[B[A]] // error: ambiguous implicit values

One way of handling such situation will be by declaring/importing the implicit manually - if it was imported from the companion, by putting it directly into the scope, the relative weight ranking algorithm will declare local implicit as more specific than one from the companion.

import A._
implicitly[B[A]].toString // "A"

That would be the issue though if you are working on automatic type class derivation and you wanted for both rules to appear in the same companion object, handling different cases.

class A
object A {
  implicit val a = new A { override def toString = "A" }
}

class B
object B {
  implicit val b = new B { override def toString = "B" }
}

class C
object C {
  implicit def a2c(implicit a: A) =
    new C { override def toString = a.toString }
  implicit def b2c(implicit b: B) =
    new C { override def toString = b.toString }
}

implicitly[C] // error: ambiguous implicit values

In such case we might affect the relative weight algorithm, by having them defined in different classes/traits:

class C
object C extends LowPriorityImplicits {
  implicit def a2c(implicit a: A) =
    new C { override def toString = a.toString }
}

trait LowPriorityImplicits { self: C.type =>
   implicit def b2c(implicit b: B) =
    new C { override def toString = b.toString }
}

implicitly[C].toString // "A"

As a matter of the fact, this is quite a popular pattern. You can find LowPriorityImplicits in scala.Predef and in virtually all more complex shapeless-based projects (e.g. the majority of Typelevel projects).

In some cases neither of these is applicable. Often in case, you have some sort of cyclic dependency between implicit definitions. As Scala compiler has troubles with such definitions at the moment, shapeless provided Lazy macro - it defers the resolution of some dependency and thus breaks the cyclic dependency.

In future versions of Scala Lazy should no longer be needed, as it will be replaced with by-name implicits.

Debugging hints

The last topic about implicits is how to debug them. Let’s face it: it is not easy.

Well, there is a flag -Xlog-implicits which prints some internal messages… but it generates tons of logs, as we always use tons of implicits - even if we don’t know about them. An example is CanBuildFrom type class which is used to describe if the transformation we are doing currently is allowed (e.g. turning a collection of pairs into Map). So if you are (flat)mapping collection implicits are there.

Some improvement over it might be the splain compiler plugin. Its author aims to make the compiler generate better error messages about implicits, which is why the plugin creates a pretty print with an implicit derivation tree.

If we are trying to debug e.g. type class derivation, my first idea is to run REPL. Then import things, so that your scope possibly close to the one you are trying to fix (you might need to commend something out, in order to make project compile and run console). Then, you have 2 tools at your disposal:

• implicitly[T] provided by scala.Predef,
• shapeless[T] from the shapeless library - it works similarly to implicitly but provides more information.

sealed trait Natural

sealed trait Zero extends Natural
object Zero extends Zero

class Succesor[N <: Natural] extends Natural

trait Add[N <: Natural, M <: Natural] {
  type Result <: Natural
}

object Add {

  implicit def zeroCase[M <: Natural]:
    Add[Zero, M] { type Result = M } = null

  implicit def succCase[N <: Natural, M <: Natural(
    implicit add: Add[N, M]
  ):
    Add[Succesor[N], M] { type Result = Succesor[add.Result] } =
     null
}

implicitly[Add[Succesor[Zero], Zero]]
// Add[Succesor[Zero], Zero] = null

import shapeless._
shapeless.the[Add[Succesor[Zero], Zero]]
// Add[Succesor[Zero], Zero]{type Result = ammonite.$sess.cmd6.Succesor[ammonite.$sess.cmd6.Zero]} = null

Another tool you should have under your belt is scala.reflect.runtime.universe.reify:

show(reify(implicitly[Add[Succesor[Zero], Succesor[Zero]]]).tree) 
// String = "Predef.implicitly[cmd7.Add[cmd6.Succesor[cmd6.Zero], cmd6.Succesor[cmd6.Zero]]](cmd7.this.Add.succCase(cmd7.this.Add.zeroCase))"

These examples should give you the general idea how these utilities work.

If I wanted to debug shapeless-generated type class I would try to:

• generate Generic.Aux (maybe using some utility function to avoid passing the other type parameter myself),
• check if derivation of intermediate HList or Coproduct works,
• check if you are able to convert generic version back to specific.

If you are terrified, that you would have to write by hand a lot of intermediate implicits, remember: you are testing derivation and resolution in REPL, not writing a production code. Usage of null.asInstanceOf[X] and ??? is perfectly fine for populating the scope with mock data.

In some cases (not many though), IDE can help you. IntelliJ has an option for showing implicits. By putting the cursor in the place you are interested and selecting View > Implicit Parameters (or Ctrl + Shift + P on non-Mac computers) you will be able to show from where the supplied implicit came from. As far as I remember it is far from perfect, but it’s better than nothing.

One last thing you can do is to customize error messages using @implicitNotFound and (since 2.12) @implicitAmbiguous. If you know beforehand, that your trait/class require some import, local definition or that the enclosing class extends some trait you can leave, that information here. This way in the future, when you forget about the assumptions error message can get you back on track much faster than if you had to reverse-engineer your thinking from the past. Same with colliding implicits - if you know which imports might clash, you can leave yourself a reminder in the annotation.

Summary

Implicits are a really useful mechanism without which Scala would not be the language it is today. They make it possible to automate a lot of code generation (type class derivation) and - if used properly - they can help express assumptions about your code (type bounds, implicit evidence).

However, this mechanism comes with a cost: they are hard to debug, might require in-depth knowledge about how resolution works and generate a lot of work for the compiler. As such, they might become dangerous in inexperienced programmers hands.

In the end, each team/project needs to weight the pros and cons themselves basing on their own values, preferences, and limitations to answer questions like how much work they want to move on to the compiler, and how much extra compile time is bearable.