ScalaTypes.md

A short journey through types in Scala

(based on the Jon Pretty's "Advanced Type Mechanics" workshop)

Type

It is a named collection of method signatures. Those method signatures are called properties.

Classes and traits vs types

We should be careful not to confuse classes or traits and types, because they are different things. Every class and trait gives rise to a type with the same name, but in itself is not a type. Many types also exist which do not solely correspond to a trait or a class.

Scala Type Hierarchy

It is an infinite directed acyclic graph of types from Nothing to Any. Nothing is called the bottom type and is an abstract class, so therefore cannot be instantiated. You probably know this:

def x: Int = ???

We can put ??? wherever we want, because Nothing is a subtype of all types.

The Scala type hierarchy is also a lattice: an algebraic structure where every pair of types will always have a supremum (least upper-bound) and an infimum (greatest lower-bound).

Quiz: Sometimes, the compiler needs to calculate the least upper-bound (the “best” type the compiler can find to describe all the types we are considering) for mutiple types. What do you think will be the type of the following?

case class A()
case class B()
List(A(), B()) // do not press enter yet :)

Subtyping

It is the ability of a compiler to take advantage of the knowledge that one type has a superset of the properties of another different type.

Subtyping vs inheritance

Subtyping should also not be confused with inheritance. If one class inherits from another, then a subtyping relationship is established, but subtyping relationships can arise without inheritance, for example, Product with Serializable is a subtype of Product.

Type bounds

def foo[T >: Nothing <: Any](a: T){}

Upper type bounds limit a type to a subtype of another type, lower type bounds declare a type to be a supertype of another type.

The previous example is a completely unbounded type, so the bounds can be omitted.

Generalized type constraints (GTCs)

They allow us, from within a type-parameterized class or trait, to further constrain its type parameters. How would we start implementing the Option's flatten method?

class Option[+A] {
  def flatten[B, A <: Option[B]]: Option[B] = ???
}
lazy val _ = new Option[Option[Int]].flatten
lazy val _ = new Option[Int].flatten // wrong!

The second example shouldn't compile, but the second type parameter A shadows the first one, so the constraint isn't taken into account. Let's use the GTC.

class Option[+A] {
  def flatten[B](implicit ev: A <:< Option[B]): Option[B] = ???
}
lazy val _ = new Option[Option[Int]].flatten
new Option[Int].flatten // correct, does not compile

The above can be achieved also with implicit conversions, but at the time the Option was implemented there were no value nor implicit classes.

GTCs are just abstract classes that take two type parameters. They can be written in infix-style.

Testing subtyping

We can use GTCs to search for implicit evidence that the type on the left is a subtype of the type on the right.

implicitly[Error <:< Throwable]
implicitly[Exception <:< Error] // does not compile

Implicit search will find the instance (i.e. compilation will succeed) if it's true.

There is also a less usefull =:= GTC for type equality.

implicitly[Int =:= Int]
implicitly[Int =:= String] // does not compile

It is most useful when one of the types in the comparison is abstract.

Infix types

class M[T, U]
new (Int M String)

GTCs are implemented as infix types.

Intersection types

An intersection of two types is a type with the union of the properties (methods) of those types.

def f[A](a: A)(implicit ev: Int with String <:< A) = a match {
  case i: Int => i
  case s: String => s.length
}
f(1)
f("aa")
f(Some(1)) // does not compile

The above is actually a compound type, which is not the intersection type in the full sense of the term. But for the purpose of this document we can assume, that they are mostly the same. In Dotty (a project name for everything around Scala 3) the keyword with is going to be replaced by &.

Union types

The type representing an intersection of the properties of two types is the least upper-bound. This is a supertype of a hypothetical type (which doesn't exist in Scala 2) which represents the union of the instances of the types. There will be union types in Scala 3 e.g. Int|String

Singleton types

object Foo {}
val x: Foo.type = Foo

Literal types

val x = "hello"
final val y = "hello" // literal type

In Dotty and Scala 2.13, we can write val x: "hello" = "hello"

Existential types (quantified on a type)

type A = Option[T] forSome { type T <: Exception }
implicitly[Option[RuntimeException] <:< A]

They are a generalization of wildcard types, and are going to be dropped in their most general form (involving the forSome keyword) in Scala 3.

Wilcards

implicitly[Option[_ <: Exception] =:= A]

Bonus: Some types are unexpressable by wildcards e.g. List[(T, T) forSome { type T }].

The type List[(_, _)] is equivalent to List[(T1, T2) forSome { type T1; type T2 }].

Path-dependent types

trait Foo { type Bar }
val foo = new Foo { type Bar = String }
val x: foo.Bar = "aaa"
val x: foo.Bar = 1 // does not compile

Projection types (existentials quantified on a value)

They are a way to select type members of other types.

val x: Foo#Bar = "aaa" // does not compile
val x: Foo#Bar = "aaa".asInstanceOf[foo.Bar]

Foo#Bar and p.Bar forSome { val p: Foo } are interchangeable.

Bonus: F-bounded polymorphism

trait Foo[T <: Foo[T]]

A type which may be parameterized by a different subtype of itself. Discouraged as introduces a lot of complexity.

Type erasure

Scala actually has two type systems. The one we discuss and the runtime type system. Some types are basically erased at runtime. For example we can`t do:

List(1, 2, 3) match {
  case xs: List[String] => None
  case xs: List[Int] => xs.headOption
}

Arrays of any dimension are an exception from this rule because they are represented natively in the JVM.

Variance

It tells us whether a generic type is a subtype of another type. Fun fact is that even the designers of the Scala type system, say that they work out the variance by trial and error. Don't feel stupid if you do the same.

Let's start with Liskov Substitution Principle: If a type T is a subtype of a type U, you can subsitute a value of type T where a value of type U is required.

class Animal
class Cat extends Animal
class Dog extends Animal

val d: Dog = new Dog
val a: Animal = d

List is covariant, so the subtyping relationship of the wrapped type follows the subtyping relationship of the type it wraps:

val d: List[Dog] = List(new Dog)
val a: List[Animal] = d

Function1 on the other hand is contravariant in the first type parameter, so the relationship is reversed:

val f: Function1[Dog, Animal] = (animal: Animal) => new Cat

The rule of thumb is that if a type has a method which returns an instance of T, then the type is covariant in T, and if a type has a method which takes an instance of T as an argument, then the type is contravariant in T.

The situation becomes more complex when considering variant types that are nested.

Example:

trait GetFun[T] {
  def get: Function1[T, String]
}

The rules are like in multiplication: every "+" encountered along the way leaves the variance unchanged, any "-" flips the variance between covariance and contravariance. So, two pluses give us a plus, two minuses also give us a plus.

We have T in which Function1 is contravariant ("-") and Function1 itself in the covariant position ("+"), which gives us "-".

trait GetFun[-T] {
  def get: Function1[T, String]
}

More complex example:

trait GetFunConsumer[T] {
  def apply(xs: List[GetFun[T]])
}

We have T in which GetFun is contravariant ("-"), GetFun in which List is covariant ("+"), and List itself in the contravariant position ("-"), which gives us "+".

trait GetFunConsumer[+T] {
  def apply(xs: List[GetFun[T]])
}

Type constructor

Any class or trait that has at least one generic parameter e.g. List[T]. They are something like functions at the type-level. List takes a proper type e.g. String and returns a proper type List[String].

List[Int] is not a type constructor (it isn`t parametrized), it is a type.

Kind - a type of a type constructor

:kind List[Int]
:kind List
:kind Either // (a binary type constructor)

Higher-kinded types - types of nested type constructors

import scala.language.higherKinds
trait Functor[C[_]]
:kind Functor

Poly-kinded types - there are two poly-kinded types Any and Nothing

def foo[T[_]] = 1
foo[List]
foo[Any]
foo[Int] // does not compile

def bar[T[_[_]]] = 1
bar[Nothing]
bar[List] // does not compile

Context bounds

def foo[T: List]: Unit = ()
foo[Int]

They constrain the type on the right-hand side to be a higher-kinded type which takes the type on the left-hand side to a proper type. The above is equal to:

def foo[T](implicit ev: List[T]) = ()

Let's test it:

implicit val i: List[Int] = List(1)
foo[Int]
foo[String] // does not compile

It's commonly used in functional programming, in places where we have to provide an instance of a typeclass like Functor.

Type lambdas

Scala also allows us to write lambdas at the type-level.

var f: Functor[({ type L[T] = T with Serializable })#L] = _

We passed an anonymous type constructor which takes some proper type and returns the intersection of that type and the Serializable trait to the Functor.

In Scala 3 type lambdas are going to be simplified to something like: [T] =>> T with Serializable.