Kinds of types in Scala

When I try to explain to someone why I prefer Scala to Java, and why functional programming works better with Scala, one of the arguments is that it has a better type system. But what exactly does it mean? What advantage does it have over the static type systems of languages like Java or Go?

Origin of types

First of all, let’s think about what types themselves are. Historically, they were introduced to solve the issue of ambiguities in mathematics, which appeared under certain conditions, and were developed as a part of the effort to formalize mathematics.

Before formalization, mathematicians needed to face paradoxes like set of all sets. Bertrand Russell described it as one of the entities we are unable to decide whether it could exist or not, without building upon strict, formal definitions. Nowadays, set theory solves this problem using Zermelo–Fraenkel axioms:

• let us assume, that the set of all sets could be constructed,
• the power set of some set is always bigger than said set,
• if this set is the set of all sets it would have to be a strict superset of itself and its own power set as well,
• this leads to the conclusion, that the set would have to be bigger than itself (not equal!),
• by contradiction we conclude, that building the set of all sets is impossible.

At the time, though, Bertrand Russell proposed another way to avoid the paradox:

• each term should be assigned a type. It is usually denoted with a colon: $2: nat$,
• if we wanted to define a function we would define on which types it operates: e.g. $times2: nat \rightarrow nat$.

$f: X \rightarrow Y$ read as: $f$ is a function from $X$ (domain) to $Y$ (codomain).

He proposed that we should build objects from bottom-up: if we define something using predicates, we can only use already defined objects and never other predicates. However, such a definition has a flaw: since we cannot reuse other predicates, we couldn’t e.g. compare cardinality of sets (how could you prove, that the types match?).

His initial (ramified) set theory was later on refined using axiom of reducibility, which allowed whole hierarchies of types to collapse creating a simple type theory. It introduced the following rule:

• terms can be converted using explicitly defined rules: e.g. $2 + 2 \twoheadrightarrow 4$ means that $2 + 2$ reduces to $4$, so it has the same type.

In 1940, Alonzo Church combined the type theory with his own lambda calculus creating simply typed lambda calculus. Since then more advanced type theories appeared.

Types, intuitively

Type theory exists in parallel to a set theory: one is not defined using the other. Because of that we cannot strictly speaking compare types to sets.

But we can if it’s about intuition. By saying the value $a$ belongs to a type $A$ ($a: A$), we can compare it to saying that value $a$ belongs to a set $A$ ($a \in A$). Saying that type $A$ is a supertype of $B$ and a subtype of $C$ is analogous to saying, that $B \subset A \subset C$. When we say that $t$ is of both types $X$ and $Y$, it is the same as saying that $t \in X \cap Y$.

If we defined a set containing all values except itself, in type theory we would call it a top type: type which contains (is a supertype of) all other types. Similarly, the empty set would have a counterpart in form of the bottom type. To make it easier to remember, imagine types as a hierarchy where more generic (less restricted) types are above and more specific (with more requirements) below. Then the type with no requirements would sit at the top and contain all values, while the type at the bottom, with requirements of all the types above it (which must be contradictory), would be empty.

In Scala

If we look how Scala implements types, we’ll see that a judgment $a: A$ ($a$ is of type $A$) is directly translated into the syntax:

val a: A
def f(a: A): B

When it comes to Scala syntax, we won’t talk about a judgment. Instead, we would talk about a type ascription. Notation for function type also comes from the type theory: $times2: int \rightarrow int$ becomes:

val times2: Int => Int

Scala has also the notion of the top and bottom types. The top type - a type we don’t have any assertions about, which contains any other type - is Any. In Java, the closest thing would be an Object, except it is not a supertype for primitives. Scala’s Any is a supertype for both objects (AnyRef) and primitives (AnyVal). When we see Any as an inferred type, it usually means we messed up and combined two unrelated types.

The bottom type - a type which is a subtype of all others, and has no citizen - in Scala is Nothing. We cannot construct a value of type Nothing, so it often appears as a parameter of empty containers or functions that can only throw.

(Quite often I see that Null is mentioned as another bottom type in Scala together with Nothing. It is a type extending everything that is an Object on JVM. So it is kind of like Nothing without primitives, Unit/void, and functions that only throw).

Also, a word about functions. In Scala we make a distinction between a function and a method. A function type is a value, which can be called:

val times2: Int => Int = x => x * 2

A method, on the other hand, is not a value. It cannot be assigned, or directly passed, though via a process called eta-expansion a method can be turned into a function.

def times2(x: Int): Int = x * 2
// val y = def times2(x: Int): Int = x * 2 - error!
val y = { def times2(x: Int): Int = x * 2 } // Unit
// however
val z: Int => Int = times2 _ // works!

Less accurate, but simpler version: a function is an instance of some Function0, Function1, …, Function22 trait, while a method is something bound to a JVM object. We make a distinction because authors of Scala haven’t solved the issue in a more elegant way.

Oh, and one more thing. With a method, you can declare an argument as implicit. You cannot do that with a function. For now. It will be possible with implicit function types in Dotty.

Type inference and Least Upper Bounds

This hierarchy of types is quite important when it comes to type inference. We expect it to provide us with the most concrete type possible, while it has to comply with any type restrictions that were imposed for a given case. Let’s take a look at a few cases:

val s = "test"

"test" has a type of String. There are no additional restrictions. So, the inferred type is String.

def a(b: Boolean) = if (b) Some(12) else None

Here, the returned value is one of two types Some[Int] or None.type (a type of None companion object). How to decide the common type for these two?

Let’s build a graph of a type hierarchy:

As we can see, there is quite a lot of candidates for the type of value returned by the function - any type which is above Some[T] and None.type at once is a valid candidate. Each of them is an upper bound for the sought type. (By analogy, if we were looking for a type of parameter we want to pass to a function, that would have to conform to several types, each of the types that would be below all of them would be a lower bound).

But having several upper bounds is not enough, it is ambiguous. However, it just happens so, that there is always one type that is the smallest of them (in a partial order meaning of smallest). Here, we can see that the Option[T] is the least of upper bounds, that fulfill our requirements. We call it the least upper bound (LUB) and it is exactly the type our function will get.

Here is why knowledge about the top type comes handy: if the inferred type is a top type (Any), among our requirements, are some that are most likely wrong, e.g. we ask Scala to find the greatest common denominator for a String and Int (List("test", 10)). Because Any is the only upper bound they share, it automatically becomes the least upper bound and the inferred type. Hardly ever we want such behavior, so it is no wonder that wartremover treats inferred Any as a code smell.

Algebraic Data Types

When we think of types as sets, there are 2 special constructions, that help us build new sets from existing ones, which complement each other. One is a Cartesian product and the other is a disjoint union/disjoint set sum.

Let’s start with a Cartesian product. We can define it as a generalization of an ordered pair. A set of ordered pairs $(A, B)$ would be a set of values $(a, b)$, such as $a \in A, b \in B$, which we could distinguish by its position inside brackets. More formally, we could define an ordered pair as (Kuratowski’s definition):

Such a definition helps us indicate the order using construction that itself has no distinction of order (that is a set).

Cartesian product generalizes the idea. It is an operator which takes 2 sets and creates a set of tuples for them:

$\{ x: p(x) \}$ is a set builder notation meaning: a set made of elements $x$ for which a predicate $p(x)$ is true

Such a definition is not associative ($(A \times B) \times C \ne A \times (B \times C)$), which we can easily check:

This is why we must explicitly define an $n$-tuple and a product of $n$ sets as a left-associative operation:

If we consider records (well, any class actually) as an $n$-tuple of its attributes and containers like lists as infinite-tuples (where all elements after some index are empty), then we’ll understand why they are called the product types and why they often share a common scala.Product trait.

type IntTwice = (Int, Int)
case class TwoInts(first: Int, second: Int)
type IntList = List[Int]
// all of the above are products

(IntList is a type alias, another name for existing type. We could use List[Int] instead of IntList and it would make no difference to Scala).

The other construct - a disjoint union, sum type or coproduct - is a sum of a finite number of sets, where no two sets have a non-empty intersection. Types are also tagged, that is we can always say from each subset originated any value of the union.

Scala 2.x doesn’t allow to actually build up a union from already existing types. If we want to let the compiler know that types should form a coproduct, we need to use a sealed hierarchy:

sealed trait Either[+A, +B] {}
case class Left[+A, +B](a: A) extends Either[A, B]
case class Right[+A, +B](b: B) extends Either[A, B]

sealed trait Option[+A] {}
case class Some[A](value: A) extends Option[A]
case object None extends Option[Nothing]

The sealed keyword makes sure that no new subtype of said class can be created outside the current file, and so the compiler will always know all types that directly inherit the trait (and form a disjoint union). This allows pattern matching to be exhaustive: compiler can tell us that we didn’t match all components of the union.

Dotty will introduce the union types, which will let us build a union out of already existing types.

def f(intOrString: Int | String) = intOrString {
  case i: Int    => ...
  case s: String => ...
}

Product types and sum types together are known as algebraic data types. They are the foundation that data modeling in functional programming builds upon.

They also allow us to use generic programming in Scala with libraries like shapeless.

Compound and intersection types

We can calculate a sum of sets (sum type), a Cartesian product of sets (product type), why not an intersection? We can declare a type belonging to several types using… the with keyword (yup, it’s more than just a mixin!).

trait Str { def str: String }
trait Count { def count: Int }

def repeat(cd: Str with Count): String =
  Iterator.fill(cd.count)(cd.str).mkString

repeat(new Str with Count {
  val str = "test"
  val count = 3
})
// "testtesttest"

It follows the mathematical definition exactly:

which means that the order of composing type using with does not matter.

val sc: Str with Count
val ca: Count with Str
def repeat(sc) // works as expected
def repeat(ca) // also works!

Well, at least when it comes to types. Since we can compose types this way we have to face a diamond problem sooner or later.

trait A { def value = 10 }
trait B extends A { override def value = super.value * 2 }
trait C extends A { override def value = super.value + 2 }
(new B with C {}).value // ???
(new C with B {}).value // ???

How would Scala deal with such cases? The answer is a trait linearization:

trait X extends A with B with C

is the same as

trait AnonymousB extends A {
  // B overrides A
  override def value = super.value * 2
}
trait AnonymousC extends AnonymousB {
  // C overrides AnonymousB
  override def value = super.value + 2
}
trait X extends AnonymousC

(implementation-wise, types B and C are not lost). If we switch the order:

trait Y extends A with C with B

then it is as if we

trait AnonymousC extends A {
  // C overrides A
  override def value = super.value + 2
}
trait AnonymousB extends AnonymousC {
  // C overrides AnonymousB
  override def value = super.value * 2
}
trait Y extends AnonymousC

It should be obvious now, that

(new B with C {}).value // (10 * 2) + 2 = 22 
(new C with B {}).value // (20 + 2) * 2 = 24

In Dotty intersection types will be denoted using &. Documentation claims that it will differ from with in a way, that Dotty wants to guarantee, that there will be no difference between A & B and B & A (operator is commutative). Currently, while A with B can be used in place of B with A and it just works, their behavior might be different due to change of order in trait linearization. Dotty will also handle parametric types intersection and intersection of properties types (List[A] & List[B] = List[A & B]). Because with has no such guarantees we call types created with it compound types instead.

Classes

In mathematics, classes came to life as a generalization of sets. In set theory, we build sets inductively from smaller elements. We cannot say about the set of all sets, as it cannot be built in such way. But what if we had another way of grouping objects, e.g. by some predicate?

A class is such group of objects for which some predicate (an indicator function, we could say) returns true.

Because a class does not have to be a set, we can talk e.g. about the class of all sets.

Programming languages borrowed the word class exactly from this concept. If we think about it, in all languages that have classes, it is basically a specification of a type/set of instances, where each member must have some set of properties and methods. It is true for:

• statically typed languages (like C/C++ where class definition dictates memory layout of an instance),
• dynamically-typed (like Python or Ruby where class is basically a factory object that creates other objects according to the spec)
• or prototype-based (like JavaScript, where the question does it have a property/methods? is extended to does it or its prototype-object have a property/method?).

Of course, in Scala, a class (and subclass) creates a new type (and subtype). Same can be said about traits.

Unit

This one is special. In lambda calculus, there are no constants, no nullary functions, and no multi-parameter functions. Everything is a single argument function returning another single argument function (therefore currying is the only way of achieving function with arity $\geq$ 1).

Similarly, in category theory, each arrow (function abstracted away from its body) goes from one object to one object (function domains/codomains abstracted away from specific values).

In such a situation, we would have to implement somehow functions returning no (meaningful) value as well as functions taking no parameters (nullary). Category theory names such irrelevant garbage input an initial object or void. It assumes that for every object you can create an arrow from void to the object (for every type there is a nullary function returning a value of this type). Since you never have the need to actually pass any value of void type (it won’t be used anyway), the set might be pretty much empty, and an actual implementation can work around it (category theory doesn’t care about the values, remember?). Thus the name void.

Similarly, there is also a final object or unit, for each object there is an arrow from an object to unit (for every type there is a function that could be fed with values of this type and doesn’t return anything useful). If it only serves the purpose of being returned, we don’t attribute it with anything meaningful. No matter how many values of this type exist, we cannot tell them apart. For us, the unit might as well be a singleton. Thus the name unit.

While creators of Scala didn’t see a point in making void an actual type (and making people confuse it with Java’s void), they did want to make sure that every function returns something. That something is (), the sole citizen of a Unit type.

Type constructors and parametric types

We can think of a type as a set. But we can also think of a function as a set, a set of parameter-returned value pairs. This lets us also think of a function signature as a type: a set of all possible sets of such pairs where arguments belong to one type and the returned value to another (where the first value from a pair is unique within the set):

• type T - a set of values

• t: T - value belonging to set T ($t \in T$)

• type S => T - a set of a subset of $S \times T$ such that each value is a function $S \rightarrow T$ (which means that first element of a pair must be unique)

  $$\{ f: (f: S \rightarrow T) \} \iff \{ f: f \subset S \times T \land \forall_{(s_1, t_1), (s_2, t_2) \in f} s_1 \neq s_2 \}$$

• f: S => T: a subset of pairs, where first element of a pair is unique

  $$f: S \rightarrow T \iff (f \subset S \times T \land \forall_{(s_1, t_1), (s_2, t_2) \in f} s_1 \neq s_2)$$

A little bit mind-numbing, but not as much as the next discovery: we could pass a set as an argument of a function and receive another set as a returned value.

Let’s build one such function:

• at first, let’s build a set of all possible types:

  $$T' = \{ T: isType(T) \}$$

• we can define a list of a type T as a function from an index (a natural number) to a value $t: T$ (which is not necessarily total function - it has no defined values after its last index)

  $$isList_T(l) = \forall_{(i, t) \in l}( i \in \mathbb{N} \land t: T \land \forall_{(i_2, t_2)} (i = i_2 \implies t = t_2 ))$$

  or shorter

  $$isList_T(l) = l: \mathbb{N} \rightarrow T$$

• now, we can build a set of all possible lists of a type $T$:

  $$L_T = \{ l: isList_T(l) \}$$

• next step would be to build a set of all possible lists of a type $T$ for each possible type $T$:

  $$L = \{ L_T: isType(T) \}$$

• finally, we can define a function which takes one $T \in T'$ and returns another set $L_T \in L$

  $List: T' \rightarrow L$ $List(T) = \{ l: isList_T(l) \}$

What we built here is a function that takes a type $T$ and returns… a type $List_T$ or List[T] using Scala’s notation.

Such a function, which takes a type and builds another type, is called a type constructor. In Scala, we could denote $List$ type constructor as List[_].

Type constructors are interesting to us because they are a mathematical way of defining parametric types, known as class templates by C++ programmers and generics by Java programmers (though, to be honest, from a mathematician’s point of view they are crippled implementations of parametric types). (You will also see this term frequently when you start reading the definitions of type classes on Haskell wiki).

Where parametric types differ from what you might know from C++ or Java is in the consequences of their functional definition. You can have a higher-order function: a function which takes and/or returns another function. Same with type constructors: you can have a type constructor, which takes and/or returns another type constructor. Many type class definitions take a type constructor as a parameter:

trait Functor[F[_]] { // <- F is a type constructor
  
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

Kinds and higher-kinded-types

These types of types (a type, a type constructor, etc) are known as kinds. Scala lets us investigate them in REPL using :kind:

scala> :kind String
String's kind is A

scala> :kind List
List's kind is F[+A]

scala> :kind Either
Either's kind is F[+A1,+A2]

scala> import scala.language.higherKinds
scala> trait NeedTC[F[_]]
scala> :kind NeedTC
NeedTC's kind is X[F[A]]

You can add a -v flag to get a detailed description with a type-theory notation ($*$ read as type):

scala> :kind -v String
String's kind is A
*
This is a proper type.

scala> :kind -v List
List's kind is F[+A]
* -(+)-> *
This is a type constructor: a 1st-order-kinded type.

scala> :kind -v Either
Either's kind is F[+A1,+A2]
* -(+)-> * -(+)-> *
This is a type constructor: a 1st-order-kinded type.

scala> import scala.language.higherKinds
scala> trait NeedTC[F[_]]
scala> :kind -v NeedTC
NeedTC's kind is X[F[A]]
(* -> *) -> *
This is a type constructor that takes type constructor(s): a higher-kinded type.

But functions allow us to do a partial application. Can we do it for types in Scala? Well, we can, but in a messy way.

scala> :kind ({ type T[A] = Map[String, A] })#T
scala.collection.immutable.Map[String,?]'s kind is F[+A]

scala> :kind -v ({ type T[A] = Map[String, A] })#T
scala.collection.immutable.Map[String,?]'s kind is F[+A]
* -(+)-> *
This is a type constructor: a 1st-order-kinded type.

(Such a thing is called a type lambda, but we’ll talk more about it when we learn more about structural and path-dependent types. Let’s skip detailed explanations for now).

Among the detailed descriptions, there are terms like 1st-order-kinds and higher-kinded types. Indeed, the same way function taking/returning functions are called higher-ordered functions, type constructors taking/returning type constructors are called higher-kinded types.

Let’s take a look at how values and functions correspond to types, and how it is reflected in types and type constructors correspondence to kinds:

and on a type level:

This table shows us how elegantly values correspond to types, functions correspond to type constructors, and function application corresponds to passing a type to a type constructor. Values can be thought of as nullary (0-argument) functions, while types can be thought of as nullary type constructors, and it still works perfectly! They are exactly the same thing, just one level of abstraction higher.

As far as I know, there are even higher levels in values-types-kinds hierarchy, such as sorts, but hardly ever there would be some practical applications for them.

Type constraints

We already talked about type bounds, and how we might impose restrictions on the inferred type just by giving it values it has to infer against. With parametric types, we might be able to do it more directly.

Let’s say we have an ADT like this:

sealed trait User { val id: Int }
case class Member(id: Int, name: String) extends User
case class Admin(id: Int, access: Set[String]) extends User

We would like to have a function that takes a list of users and returns a map from id to a user… except we would like that map to adjust: if we pass a set of Users it should return a Map[Int, User], if we pass a set of Members it should return a Map[Int, Member].

Our first attempt would probably look like this:

def byId(users: Set[User]): Map[Int, User] =
  users.map { u => u.id -> u }.toMap

It works, but it is not generic. We wanted it to be generic.

def byId[U](users: Set[U])(getId: U => Int): Map[Int, U] =
  users.map { u => getId(u) -> u }.toMap

It also works, but it forces us to pass an extractor every time - not a bad idea if it did something different each time, but it only needs to get the same property all our cases share via the User class. If only there was a way to suggest to the type system that U needs to extend User (or has User as an upper bound), and then make use of its properties…

As a matter of fact, there is.

def byId[U <: User](users: Set[U]): Map[Int, U] =
  users.map { u => u.id -> u }.toMap

byId(users: Set[Member]) // Map[Int, Member]

<: denotes an upper bound in type parameters. It looks like this, so that parser would not confuse it with <, but its meaning is similar - a type on the left is smaller (lies lower in hierarchy) than a type on the right. There is also a notation for lower bound, >::

def recover[E, A, B >: A](
    either: Either[E, A])(f: E => B): Either[E, B] =
  either match {
    case Left(e)  => Right(f(e))
    case Right(a) => Right(a)
  }

recover[String, Admin, User](err: Either[String, Admin]) {
    _ =>
  fallback: Member
}
// Either[String, User]

These are the type constraints provided by the language. Besides them there are also generalized type constraints, which exist as type classes provided by the compiler (if the compiler cannot create them, it means that a type fails the constraints):

• <:< - let us require that one type is a subclass of the other.

  def upcast[A, B](set: Set[A])(
    implicit ev: A <:< B
  ): Set[B] = set.map(ev(_))
    
  upcast[Member, User](Set(m: Member)) // Set[User]
  

  It is defined inside a scala.Predef.

• =:= - let us require that one is equal to the other.

  def update[A, B](set: Set[A])(f: A => B)(
    implicit ev: A =:= B
  ): Set[B] = set.map(f)
    
  val members: Set[Member]
    
  update[Member, Member](members)(identity) // ok
  update[Member, User](members) { member =>
    member: User
  } // compilation error!
  

  It is defined inside a scala.Predef as well.

• <%< - already removed from Scala, but it used to denote that type A is either a subtype of B or could be implicitly converted to it.

• =:!= - provided by shapeless. Proves that types are different.

If you require that there be a type class in scope for your type parameter:

def doSomething[F[_]: Monad]: F[String]

I met people who would also call implicit syntax for type classes a type constraint (I require of a type T to be a monad).

Variance

Type constraints are useful when we want to describe our expectations about a type parameter and/or the returned type. But there are use cases where they are not enough.

Let’s take a look at Option. The first implementation would be something like:

sealed trait Option[T] {}
case class Some[T](value: T) extends Option[T]
case class None[T]() extends Option[T]

It is not something we are used to. We don’t want to create a new None for each type. Actually, we want just one case object, which we could use as a valid Option[T] everywhere. However, if we tried to:

sealed trait Option[T] {}
case class Some[T](value: T) extends Option[T]
case object None extends Option[Nothing]

then, when we try to use None as Option[String] or Option[Int] we would get a type error.

def f(stringOpt: Option[String]): Unit
f(None) // compilation error!

The reason for that is that we defined the Option as an invariant parametric type. Invariance means, that even if B <: A then Option[B] still cannot be substituted for Option[A]. It is a default and a good one!

A long time ago, Java let us do such things with arrays. In Java, you can create Array[Member] and pass it as a valid parameter for a function expecting Array[User]. That function assumes that the array can contain anything as long as it’s a User, so it can insert an Admin into the array. Then you end up with a java.lang.ArrayStoreException. Suddenly you have a reference to an array of Members that contains an Admin - the JVM recognizes such a state as invalid. To avoid repetition of this problem, when Java introduced generics, it made them invariant without an option to change the behavior.

But the issue only appears if you share a mutable state. If you have an immutable object, you can, for example, pass List[Member] as List[User], Option[B] as Option[A], and you would never end up with invalid behavior (if we modified something, we would create a modified copy, so the original would still fulfill its requirements).

A situation in which we explicitly state that if B :> A then F[B] :> F[A] is called covariance. To mark a type parameter as covariant we use +:

sealed trait Option[+T] {}
case class Some[+T](value: T) extends Option[T]
case object None extends Option[Nothing]

Covariance propagates down, so if we made T in Option covariant, we will receive complaints if we don’t do the same for T in Some. Usually, when we mark the parameter as covariant and we extend the type as an object, e.g. an empty container (None, Nil, EmptySet), we use Nothing as a hardcoded type - as the bottom type it subtypes all types, so such an object can always be upcast. Additionally, it is a nice explanation that this container is empty, as it is literally a container of nothing.

(As we can guess, most immutable collections would be covariant, while most, if not all, mutable collections are invariant).

It is quite common to have a situation where we want to pass a value of a specific parametric type and generalize it. What about the opposite situation, when we have a producer of values of a parametric type and we want to specify it:

trait Consumer[T] {
  def consume(value: T): Unit
}

val members: List[Member]
def consumer: Consumer[User]
members.foreach(consumer.consume) // error!

The case where we want to say that A <: B implies F[B] >: F[A] is called contravariance, as it is an opposition of covariance. We denote it with a - sign:

trait Consumer[-T] {
  def consume(value: T): Unit
}

val members: List[Member]
def consumer: Consumer[User]
members.foreach(consumer.consume) // works

By analogy with covariance and the bottom type Nothing, Any (the top type) would be the type parameter of a consumer that consumes any value.

Covariance and contravariance are very important to functional programming in Scala. They allow for intuitive behavior for the central element of the function-as-a-first-class-citizen approach, which is the function itself:

trait Function[-A, +B] {
  def apply(a: A): B
}

It is obvious to us that a function that takes User should also take Member, and a function returning Member could be used as a substitute for a function taking User. This also shows us that invariance, covariance, and contravariance - known together as variance - describe a type parameter and not the whole type. Here A is a contravariant type parameter of Function while B is a covariant type parameter.

(Actually, Scala’s function definition looks a little bit different - and depends on its arity - but the principle holds. It also holds for a type derived from a function, a PartialFunction).

Type theory also allows bivariance - a case when the type is covariant and contravariant at the same time - but Scala doesn’t allow such a situation.

Existential types

We talked a bit about type parameters, how we can put constraints on them, and how they translate to a whole type being a super/subtype. But what should we do when we don’t care?

def count[T](seqs: Seq[T]*): Int = seqs.map(_.size).sum

count(Seq(1,2,3), Seq("test")) // 4

Here, we don’t actually use the type T at all. It should work for all Ts we pass (if we add some type constraints, then for all T that match them). So, we can describe this function with a universal quantifier:

Because we can describe it with a universal quantifier, we could call the type Seq[T] (and Seq[Seq[T]]) a universal type.

But what if our function count were part of another function or a class, and it was the only place where we needed T, so we would have to pass it down anyway? Or what if we wanted to store Sequences in a map but didn’t care about the type, because each of them would be of some other type? (ClassTag[T] -> Set[T]).

If this were Java, we could use ? to indicate that we don’t care about the type:

int count(java.util.List<?>... seqs) {
   return Arrays.stream(seqs).mapToInt(seq -> seq.size()).sum();
}

This ? tells us something like we know that there is some concrete T we could put here, but we don’t care about it at the moment. We don’t know any details about this T and, to be honest, we don’t care. All we need is the assumption that there is one. In math, we could express that with an existential qualifier:

By analogy, we could name such a type an existential type. Scala lets us express it in two ways:

def count(seqs: (Seq[T] forSome {type T})*): Int = 
  seqs.map(_.size).sum

forSome is a syntax existing solely for existential types, I believe. The other, shorter version is:

def count(seqs: Seq[_]*): Int = 
  seqs.map(_.size).sum

which looks dangerously similar to type constructor syntax. As a matter of fact, we can distinguish these two different usages merely by the context in which they appear: if F[_] appears in the definition of a type parameter it is a type constructor; if it is used as the type of a variable or parameter it is an existential type.

There are a few things that would be difficult to implement without existential types (fixed-point types in recursion schemes, I guess?), but in our everyday life, we don’t use them that often. During his work on Dotty, Odersky found out that some of their applications were among the things making the language unsound, which is why forSome notation is removed from Dotty.

When a mathematician says that some theory is sound, all formulas in the theory can be logically derived from the axioms and rules of the theory.

In the case of a type system, it means that if our type system decides that some expression has a type T, then if you run it, the returned value will also be of type T.

It might be surprising for some, but (besides null, which breaks most type systems that allow it and everybody is aware of that) there are a lot of cases when a language can be broken and forced to return a value of an invalid type.

F-bound types

The last type-parameter-related types I want to talk about are F-bound types. The name originates from the F-type system, which was the first one that allowed their existence. But what are they and what problem do they solve? Let’s look at an example:

trait Number {
  
  def +(number: Number): Number
  def *(number: Number): Number
}

class Int extends Number {
  
  def +(number: Number): Number
  def *(number: Number): Number
}

class Double extends Number {
  
  def +(number: Number): Number
  def *(number: Number): Number
}

val a: Int
val b: Int
val c = a + b // Number!

In our example, if we defined our interface without any type parameters, we would end up with a situation where any value of a specific Number would lose information about its specific type. Also, without any notice it would allow additions of unrelated implementations:

val a: Char // Char extends Number
val b: Double
val c = a + b // Number, but what Number exactly?

We might make our type Number parametric so that we could control the type of parameters and returned values:

trait Number[N] {
  
  def +(number: N): N
  def *(number: N): N
}

class Int extends Number[Int] {
  
  def +(number: Int): Int
  def *(number: Int): Int
}

class Double extends Number[Double] {
  
  def +(number: Double): Double
  def *(number: Double): Double
}

val a: Int
val b: Int
val c = a + b // Int!

The issue with operations on unrelated implementations also disappears:

val a: Char
val b: Double
val c = a + b // error!

However, now we have a new issue:

class User extends Number[Int] // why is that a thing?

What we need here is some sort of restriction where we require that a type parameter must be the type that extends the parameterized type. In Scala, we can do it in two ways:

• using self-types:

  trait Number[N] { self: N =>
    // ...
  }
  

  (we’ll talk more about self-types later on),

• using type constraints:

  trait Number[N <: Number[_]] {
    // ...
  }
  

  (Here Number[_] is an existential type, not a type constructor).

  This definition relies on a certain limitation of Scala (and Java) - we cannot implement the same parametrized type with different parameters in one class. Therefore:

  class Double extends Number[Double]
  class X extends Number[Double] // fails - different type params in Numbers
  class Y extends Number[String] // fails - string is not a Number
  

Both ways help us ensure that the implementation is type-recursive.

This is quite a popular way of solving the initial problem in languages that don’t support (or encourage) type classes. In Java, it is a built-in method of implementing Enums (enum X becomes abstract class X extends Enum[X]). C++ knows F-bound types under the name Curiously Recurring Template Pattern (CRTP).

This pattern is certainly less encouraged in languages that DO support type classes (and do not support classes and inheritance, which means half the FP languages).

Structural and refined types

We know that in math a class is a collection of objects that fulfill some conditions, and in programming we borrowed the idea. But what if we wanted to specify these conditions without giving them a name? In JavaScript, you can define a type like:

type User = { name: string, surname: string }

By most OOP languages’ standards, it is not a class. But in JavaScript and Go (and in mathematics), this is an allowed method to create a collection of values by a predicate (has name property of type string and surname property of type string) - in other words a type.

Scala also allows us to define a type this way:

type User = {
  val name: String
  val surname: String
}

We don’t have to extend User to make a value conform to the type - it is enough to fulfill the requirements:

case class Somebody(name: String, surname: String)

def needUser(user: User): Unit

needUser(Somebody("test", "test")) // works!

We can call User a structural type. It is an interesting way of implementing a type, one where compiler checks if object has all the right methods and fields instead of scanning the class hierarchy. A problem with such an approach is that at runtime Scala has to use runtime reflection to access these fields, so it comes with a performance penalty.

Structural types are not restricted to definitions using only vals and defs. We can demand that it extend some class as well:

trait X { val x: String }
type Y = { val y: Int }
val z: X with Y = new X { val x = "test"; val y = 0 }

So a compound type containing a structural type is also a structural type.

The example above shows us another interesting thing. If we asked the REPL about the type of:

new X { val x = "test"; val y = 0 }

the answer would be:

AnyRef with X{val y: Int}

Scala automatically adds the information about new fields and methods to the type! Actually, any time we add something extra to the interface, if we don’t upcast the returned value, Scala will reflect these extra properties in its type. We call such types the refined types, but they are just a special case of structural types.

It appears refined types are not unique to Scala. When local type inference arrived in Java, it also started to support them, though in a half-baked way. You cannot declare a structural type, so such types can only be used via vars, which hold information about refinement. This incomplete implementation can lead some Java programmers to think that such a feature is dangerous.

Path-dependent types

Let’s say we want to model a card game:

case class Card(color: String, value: String)
case class Player(name: String)
class Game {
  
  def getPlayers: Set[Player] = ???
  
  def getCards: Set[Card] = ???
  
  def playerPlayCard(player: Player, card: Card): Unit = ???
}

However, in our application there could be several games running at once, so we are at risk of messing up objects from different games:

val game1: Game
val game2: Game
game1.playerPlayCard(game2.getPlayers.head,
                     game2.getCards.head)

Could we make sure that we can only use objects from the right Game and do it at compile time (assertions throwing at runtime might be a little too late for our needs)?

Path-dependent types are a way of stating that the type of one object depends on another object. It is a limited version of the more generic idea of dependent types. Actually, Dotty derives its name from Dependent Object Types calculus that Odersky designed to make future versions of Scala sound.

So, how could we define such a type?

class Game {
  
  case class Card(color: String, value: String)
  case class Player(name: String)
  
  def getPlayers: Set[this.Player] = ???
  
  def getCards: Set[this.Card] = ???
  
  def playerPlayCard(player: this.Player, card: this.Card): Unit = ???
}

Let’s check what types will have values returned from game1 and game2:

val game1 = new Game
val game2 = new Game
game1.getPlayers // Set[game1.Player]
game2.getPlayers // Set[game2.Player]

We get different types, so we can expect that we cannot substitute one for the other:

game1.playerPlayCard(game2.getPlayers.head,
                     game2.getCards.head) // fails!

To create a path-dependent type, all we need to do is declare a type inside another type! It doesn’t have to be a class:

class X {
  type Y = String
  val y: Y = "y"
}

val x1 = new X
val x2 = new X

However, if it’s just a type alias, Scala can prove that two types are the same, and so it will not help us much:

def y(x: X)(y: x.Y): Unit = ()

y(x1)(x2.y) // no complaints: x1.Y = String = x2.Y

That is, unless we make it a little less obvious that the types are equal:

trait X {
  type Y = String
  val y: Y = "y"
}

class X2 extends X

val x1 = new X2
val x2 = new X2

y(x1)(x2.y) // fails!

It is not obvious anymore because we could e.g. make the type Y abstract:

trait X {
  type Y
  val y: Y
}

val x1 = new X {
  type Y = String
  val y: Y = "y"
}
val x2 = new X {
  type Y = Int
  val y: Y = 1
}

OK, but what if we wanted to relax our requirements at some point?

def takeAnyPlayer(p: ???): Unit

We need a way of passing a path-dependent type without its context if needed. This is possible via #:

def takeAnyPlayer(p: Game#Player): Unit

At this point there is very little we know for certain about our p. Scala most likely won’t be able to tell what the exact type is even if it would be obvious to you from the code. If there were some type constraints about the type, that would be guaranteed, you can rely on it. But anything that comes with the specification of path-dependent type is lost:

trait X {
  type Y <: AnyVal { def toLong: Long }
  val y: Y
}

val x1 = new X {
  override type Y = Int
  override val y: Y = 1
}
val x2 = new X {
  override type Y = Long
  override val y: Y = 1L
}

Hmm, here our type Y is defined directly inside a X instance, so Scala should be able to guess its exact type. We can confirm that indeed it is:

x1.y * x1.y // 1: Int
x2.y * x2.y // 1: Long

Similarly for #:

scala> trait X { type Y }
scala> :kind (X { type Y = Int })#Y
// Int's kind is A

We can use path-dependent types as a method return type (path-dependent methods). However, we are not allowed to create a function that uses path-dependent types. It will be introduced in Dotty under the name dependent function types.

Kind projector/type lambda

At this point we have enough information to understand what was happening inside some weird construction we used during partial application in a type constructor with multiple type parameters:

scala> :kind ({ type T[A] = Either[String, A] })#T
scala.util.Either[String,?]'s kind is F[+A]

We start with Either[_, _] and we want to partially apply String as the first type parameter. In order to do so, we:

• create a type alias T[A] = Either[String, A], which creates a parametric type T[A] with one type parameter,
• we put it inside a structural type to create an opportunity for creating a path-dependent type,
• finally we extract T as a path-dependent type, such that Scala can tell its specific type exactly,
• since we didn’t apply type parameters, we end up with a single parameter type constructor,
• we achieved partial-application of a type parameters to a type constructor, aka type lambda or kind projection.

Quite often kind projectors use λ to denote the output type. Because the syntax is quite messy, you might prefer to use a dedicated compiler plugin that would generate it for you. With kind-projector compiler plugin you would need to write just:

Either[String, ?]

In Dotty, type lambdas are supported natively with the syntax:

[T] => Either[String, T]

Kind projectors become more useful the more you dive into hardcore functional programming as promoted by Cats and Scalaz.

Self-types

Mixins. Sometimes we want to add some functionality to an existing class and traits are a great way of achieving that:

class Producer {
  
  def produce: Int = 1
}

trait DoubleProducer extends Producer {
  
  override def produce: Int = super.produce * 2
}

trait IncreaseProducer extends Producer {
  
  override def produce: Int = super.produce + 1
}

class MyProducer extends Producer with DoubleProducer with IncreaseProducer

(new MyProducer).produce // 3

Thing is, if we do it that way, we cannot make Producer a trait or abstract class. Perhaps we would like to use it only as an interface, and then decorate the implementation (one of many).

In Scala, sometimes we need to refer to the current instance. Usually, we might use this, but if we nest type definitions, this will only point to the one we are currently inside. It makes it hard to access the outer object. We can give a name to this to make it less ambiguous:

trait Outer { self =>
  
  trait Inner {
    self // Outer
    this // self.Inner
  }
}

However, we might use type ascription to put a constraint on this self value (or whatever we decide to name it):

trait Producer {
  
  def produce: Int
}

trait DoubleProducer { self: Producer =>
  
  override def produce: Int = super.produce * 2
}

As we can see, we no longer need to extend decorated type - type ascription already allows us to access the decorated type’s members. Additionally, this self-type acts as a type constraint on any type, that would like to mix-in the trait.

class OneProducer extends Producer {
  def produce: Int = 0
}

class MyProducer extends OneProducer with DoubleProducer // OK
class Invalid extends Producer with DoubleProducer // error!

Self-types might be used to enforce ordering of low-priority implicits:

object MyType extends MyTypeImplicits

trait MyTypeImplicits extends MyTypeLowPriorityImplicits {
  
  // implicits
}

trait MyTypeLowPriorityImplicits { self: MyTypeImplicits =>
  
  // low-priority implicits
}

That is not the only use case though. Some people use self-types as a way of type-safe dependency injection:

trait FirstServiceComponent {
  
  trait FirstService
  val firstService: FirstService
}

trait SecondServiceComponent {
  
  trait SecondService
  val secondService: SecondService
}

trait FirstServiceComponentImpl extends FirstServiceComponent {
    self: SecondServiceComponent =>
  
  val firstService = new FirstService {
    // use secondService
  }
}

trait SecondServiceComponentImpl extends SecondServiceComponent {
    self: FirstServiceComponent => 
  
  val secondService = new SecondService {
    // use firstService
  }
}

object Application
    extends FirstServiceComponentImpl
    with SecondServiceComponentImpl

Each component of such a construct is called a layer. When we compose layers together, we are baking a cake. This metaphor is the origin of the name of this pattern - a cake pattern. Many programmers and I discovered that such a bastardized mixin causes more troubles than it solves. Problems with extensions, maintenance and initialization order I already described in another article.

Creating new types out of existing: tagged and value types

Sometimes we don’t want to create a completely new product with 2 or more fields, nor a sum type. We also don’t want to use type alias, which doesn’t create a distinct type. We might want something like Surname or Name which is like String, but with no risk of accidentally passing values in the wrong way (surname as name, name as surname).

One way of handling these issues was designed by Miles Sabin for shapeless; the other one was provided by the language authors.

The solution proposed by Miles Sabin works by tricking the compiler into believing that our value is of a type it is not:

object tag {
  def apply[U] = new Tagger[U]

  trait Tagged[U]
  type @@[+T, U] = T with Tagged[U]

  class Tagger[U] {
    def apply[T](t : T) : T @@ U = t.asInstanceOf[T @@ U]
  }
}

To understand this, let us see an example:

sealed trait Name
sealed trait Surname

val name = tag[Name]("John") // String @@ Name
val surname = tag[Surname]("Smith") // String @@ Surname

This @@ construct takes two types: our initial type (for which we provide a value) and another type called a tag, which will serve as a way of making a newly created type unique. We can always demand a type String with Tagged[Name] (or String @@ Name if you prefer) - the fact that String is final is checked only during class declaration and the mismatch between String with Tagged[Name] could only be found at runtime.

Meanwhile, the only methods we will have declared will be methods from String - which our value surely is. JVM will never have an opportunity to complain, so as long as compiler is OK about it, it will work. It appears, that .asInstanceOf[String @@ Name] is enough to silence it.

Tagged types require that we define a trait/class that will serve as a tag. They can quite often be sealed traits that you won’t use anywhere else. As long as you have the tags, you can easily lift any type to a tagged type. In runtime, they will be untagged though, which might be advantage or disadvantage depending on situation (runtime reflection!). In compile time they will create different types, so you have to take that into consideration if you are using any type-level programming - type classes provided for primitives won’t work with tagged types (there is no one-standard for tagging) and you will have to handle it yourself.

To provide a standard solution to the mentioned problem, Scala came up with value types. A value type is basically a class extending AnyVal with one val member.

// for convenience people prefer to use case classes for it
case class Name(value: String) extends AnyVal

// though it is not required
class Surname(val value: String) extends AnyVal
object Surname {
  def apply(value: String): Surname = new Surname(value)
}

Since there are few restrictions imposed on this class, the compiler has a lot of opportunities to optimize the wrapper away. Since it is a standard solution, many libraries handle it out of the box. The disadvantage is that the optimization doesn’t work reliably, so e.g. mocking is almost completely broken (because sometimes the value is boxed and sometimes wrapper is optimized away).

As some sort of middle ground, a newtype library was designed.

@newtype case class Name(value: String)

It lets you declare your new type as a case class (which helps with IDE support), while a macro annotation rewrites it into:

type Name = Name.Type
object Name {
  type Repr = String
  type Base = Any { type Name$newtype }
  trait Tag extends Any
  type Type <: Base with Tag

  def apply(x: String): Name = x.asInstanceOf[Name]

  // here AnyVal is used as extension methods optimization
  implicit final class Ops$newtype(val $this$: Type) extends AnyVal {
    def value: String = $this$.asInstanceOf[String]
  }
}

Phantom and literal types

sealed traits for each tag would pollute the JVM with unused interfaces. Could that be avoided? Well, it is planned.

There is a pattern for implementing something that is basically a type-level state machine.

sealed trait Switch
sealed trait On extends Switch
sealed trait Off extends Switch

class Bulb[S <: Switch] {
  
  def turnOn(implicit ev: S =:!= On): Bulb[On] =
    new Bulb[On]
  
  def turnOff(implicit ev: S =:!= Off): Bulb[Off] =
    new Bulb[Off]
}

val bulb = new Bulb[Off]
bulb.turnOff // error!
bulb.turnOn // Bulb[On]
bulb.turnOn.turnOn // error!
bulb.turnOn.turnOff // Bulb[Off]

Because Switch, On and Off are not used for anything other than indicating the state with a type, they are called phantom types. Currently, it is just a pattern, but Dotty will let us mark a type as an erased term, which makes it exist only in compile time.

Another type-level-specific thing that will arrive — this time with Scala 2.13 — is a literal type. With libraries like shapeless you can express e.g. case class as a HList. Thing is, it only stores information about types and their positions. There is no information about properties names, so generating things like JSON codecs is impossible. Or would be if not for LabelledGenerics, which return HList of tuples of Witness-types. Wait, what is a Witness? Let’s try to figure out from an example:

case class Test(a: String, b: Int)

def getGeneric[T, U](
  t: T)(implicit gen: Generic.Aux[T, U]): U = gen.to(t) 
def getLabelledGeneric[T, U](
  t: T)(implicit gen: LabelledGeneric.Aux[T, U]): U = gen.to(t)

getGeneric(test) // String :: Int :: HNil = "xyz" :: 1 :: HNil
getLabelledGeneric(test) 
// labelled.FieldType[Symbol @@ a, String] ::
//   labelled.FieldType[Symbol @@ b, Int] ::
//   ops.hlist.ZipWithKeys.hnilZipWithKeys.Out =
//     "xyz" :: 1 :: HNil

Interestingly, the LabelledGeneric created an instance, which stores the name of the field it originated from! (FieldType works the same way as tagged types - no extra information in runtime, but extra data in compile time).

It appears that the compiler can create a singleton type of just one value. Since it is defined by its literal it is also known as a literal type. But even if compiler knows such types, it doesn’t let us create one… without some hacking.

Witness is a helper trait which implementation is provided by a shapeless macro:

trait Witness extends Serializable {
  type T
  val value: T {}
}

object Witness extends Dynamic {
  type Aux[T0] = Witness { type T = T0 }
  type Lt[Lub] = Witness { type T <: Lub }

  implicit def apply[T]: Witness.Aux[T] =
    macro SingletonTypeMacros.materializeImpl[T]

  implicit def apply[T](t: T): Witness.Lt[T] =
    macro SingletonTypeMacros.convertImpl
  
  // ...
}

These macros let us currently access the literal types, which is so far accessible only via compiler internals. But with Scala 2.13 they will become available without costly hacks in the language.

Summary

In this article, I intended to talk a bit about types in Scala from the perspective of type and set theories, but also explain certain idiosyncrasies of Scala when it comes to implementing them.

We can see that Scala has quite a powerful type system which is only going to get better. Even on its own, it is enough to give Scala a competitive edge over many other languages. It has allowed the development of many features which would be otherwise hard to implement, fragile or impossible.