#type classes

Preventing "Nothing" Inference

Type Nothing has very interesting property by being a bottom type, which means that it's a subtype of all other classes. And it turns out that you can use (or misuse) this property in order to implement a type class, that can detect that something is not Nothing, because all other classes simply don't have this property (except other bottom types). So lets define NotNothing type class:

@implicitNotFound("Sorry, type inference was unable to figure out the type. You need to provide it explicitly.") trait NotNothing[T] object NotNothing { private val evidence: NotNothing[Any] = new Object with NotNothing[Any] implicit def notNothingEv[T](implicit n: T =:= T): NotNothing[T] = evidence.asInstanceOf[NotNothing[T]] }

Interestingly enough compiler would not be able to find an NotNothing[Nothing] evidence in this case. It still puzzles me why exactly this is the case, but looks like it has something to do with type inference algorithm. I made a small experiment that shows, that as soon as compiler tries to infer T, then =:= will fail for Nothing:

scala> def foo[T](implicit a: T =:= T) = a foo: [T](implicit a: =:=[T,T])=:=[T,T] scala> foo[Nothing] res2: =:=[Nothing,Nothing] = <function1> scala> foo <console>:9: error: type mismatch; found : =:=[Nothing,Nothing] required: =:=[T,T] Note: Nothing <: T, but class =:= is invariant in type From. You may wish to investigate a wildcard type such as `_ <: T`. (SLS 3.2.10) Note: Nothing <: T, but class =:= is invariant in type To. You may wish to investigate a wildcard type such as `_ <: T`. (SLS 3.2.10) foo ^

If you know exactly how and why it works like this, then I would appreciate it you share it in the comments.

Anyways, this seem to work, so let's define inject method in terms of NotNothing:

def inject[T](implicit tt: TypeTag[T], nn: NotNothing[T]) = tt.toString

and then test it in REPL:

scala> inject <console>:12: error: Sorry, type inference was unable to figure out the type. You need to provide it explicitly. inject ^ scala> inject[Nothing] <console>:12: error: Sorry, type inference was unable to figure out the type. You need to provide it explicitly. inject[Nothing] ^ scala> val foo: String = inject <console>:11: error: Sorry, type inference was unable to figure out the type. You need to provide it explicitly. val foo: String = inject ^ scala> inject[String] res6: String = TypeTag[String] scala> inject[Int] res7: String = TypeTag[Int]

As you can see, it works as expected - code does not compile as soon as Nothing is involved. And as a bonus, you can even specify a nice error message with implicitNotFound annotation.

Implementing "Not" Type Class

It this point I decided to bring this idea even further. If I'm able to produce an evidence that some type T is not Nothing, then I also should be able to prove, that some type T is does not have some evidence. It actually was my dream for quite some time to be able to get an evidence that some other evidence does not exist rather than get an evidence when it exists (which is the standard ways to work with type classes). It turns out that it's not only possible, but also pretty straightforward to implement.

In order to do this, we need some type to represent an existence/non-existence:

sealed trait Existence trait Exists extends Existence trait NotExists extends Existence

Now lets create a type class, that can prove, that some other evidence exists or does not exist:

trait IsTypeClassExists[TypeClass, Answer] object IsTypeClassExists { private val evidence: IsTypeClassExists[Any, Any] = new Object with IsTypeClassExists[Any, Any] implicit def typeClassExistsEv[TypeClass, Answer](implicit a: TypeClass) = evidence.asInstanceOf[IsTypeClassExists[TypeClass, Exists]] implicit def typeClassNotExistsEv[TypeClass, Answer] = evidence.asInstanceOf[IsTypeClassExists[TypeClass, NotExists]] }

And finally lets implement Not type class, that can be easily expressed in terms of IsTypeClassExists:

@implicitNotFound("Argument does not satisfy constraints: Not ${T}") trait Not[T] object Not { private val evidence: Not[Any] = new Object with Not[Any] implicit def notEv[T, Answer](implicit a: IsTypeClassExists[T, Answer], ne: Answer =:= NotExists) = evidence.asInstanceOf[Not[T]] }

This type class is pretty powerful and can give us a proof, that some other type class does not exist for some arbitrary type T. Lets first reimplement inject method in terms of Not:

def inject[T](implicit tt: TypeTag[T], nn: Not[T =:= Nothing]) = tt.toString

and repeat our REPL session:

scala> inject <console>:11: error: Argument does not satisfy constraints: Not =:=[T,Nothing] inject ^ scala> inject[Nothing] <console>:11: error: Argument does not satisfy constraints: Not =:=[Nothing,Nothing] inject[Nothing] ^ scala> val foo: String = inject <console>:10: error: Argument does not satisfy constraints: Not =:=[T,Nothing] val foo: String = inject ^ scala> inject[String] res3: String = TypeTag[String] scala> inject[Int] res4: String = TypeTag[Int]

As you can see, it behaves exactly like previous version, but now it's implemented in much more generic way. Error message is a little bit more cryptic but I find it pretty straightforward to understand it's meaning.

Describing Arbitrary Complex Type Constraints

In order to make this picture complete, we are still missing Or and And type classes. Implementing these should be even easier than Not, so let's start with And:

@implicitNotFound("Argument does not satisfy constraints: ${A} And ${B}") trait And[A, B] object And { private val evidence: And[Any, Any] = new Object with And[Any, Any] implicit def bothExistEv[A, B](implicit a: A, b: B) = evidence.asInstanceOf[And[A, B]] }

and Or:

@implicitNotFound("Argument does not satisfy constraints: ${A} Or ${B}") trait Or[A, B] object Or { private val evidence: Or[Any, Any] = new Object with Or[Any, Any] implicit def aExistsEv[A, B](implicit a: A) = evidence.asInstanceOf[Or[A, B]] implicit def bExistsEv[A, B](implicit b: B) = evidence.asInstanceOf[Or[A, B]] }

Now we should be able to describe any kind of logical expressions, that constrain the type, in the method signature. Let's go though some examples.

Union types? No problem whatsoever

def union[T](t: T)(implicit c: (T =:= String) Or (T =:= Int)) = t match { case s: String => println(s"Some nice string: $s") case i: Int => println(s"Some int: $i") }

or if like, you can define nice type lambda:

type V[A, B] = {type l[T] = (T <:< A) Or (T <:< B)} def union[T: (String V Int)#l](t: T) = t match { case s: String => println(s"Some nice string: $s") case i: Int => println(s"Some int: $i") }

and make sure that it works as expected:

scala> union("Test") Some nice string: Test scala> union(265) Some int: 265 scala> union(2.0) <console>:11: error: Argument does not satisfy constraints: =:=[Double,String] Or =:=[Double,Int] union(2.0) ^

More complex examples

Here I want to sort the list of any element type except lists with strings and numbers in it

def sort[T: Ordering](list: List[T])(implicit c: Not[(T =:= String) Or Numeric[T]]) = list.sorted

Or in this example I want method to accept only specific colors:

sealed trait Color case object Red extends Color case object Green extends Color case object Blue extends Color case object Yellow extends Color case object Magenta extends Color def printColor[T](t: T)(implicit c: (T =:= Red.type) Or (T =:= Green.type) Or (T =:= Magenta.type)) = println(t)

or instead of defining a whitelist, I can define a blacklist:

def printColor[T](t: T)(implicit c: (T <:< Color) And Not[T =:= Color] And Not[(T =:= Yellow.type) Or (T =:= Blue.type)]) = println(t)

and in REPL:

scala> printColor(Yellow) <console>:11: error: Argument does not satisfy constraints: And[<:<[Yellow.type,Color],Not[=:=[Yellow.type,Color]]] And Not[Or[=:=[Yellow.type,Yellow.type],=:=[Yellow.type,Blue.type]]] printColor(Yellow) ^ scala> val c: Color = Magenta c: Color = Magenta scala> printColor(c) <console>:12: error: Argument does not satisfy constraints: And[<:<[Color,Color],Not[=:=[Color,Color]]] And Not[Or[=:=[Color,Yellow.type],=:=[Color,Blue.type]]] printColor(c) ^ scala> printColor(Magenta) Magenta