Existential Types in Scala

In the first blog of the Scala Type System series, I  had put a lot of emphasis on the fact that “Type variables make a very powerful piece of type-level programming.” They appear in a variety of forms and variations. One of the important forms is “existential types.” In today’s blog, I would like to get you familiar with the existential types.

Given below is a typical way of defining a variable:

type F[A] = SomeClass[A]

Where A is said to be a type variable. Notice that A has appeared on both sides of the above equation. This implies that F is fully dependent on A. The type of A is essential for instantiation of the SomeClass. Let us take a few examples:

sealed trait F[A]
final case class SomeClass[A](a: A) extends F[A]

SomeClass("hello"): F[String]      
SomeClass(1: Int): F[Int]
SomeClass(true): F[Boolean]
SomeClass("hello"): F[Int]

Notice that the last example would not compile as the Type A on the LHS and RHS of the equation conflict.

Let us understand the need for existential types. Consider the following is defined as:

def getLength(x : Array[Any]): Int = x.length

val stringArray = Array[String]("foo", "bar", "baz")

getLength(stringArray)

The above line gives us the following error:

error: type mismatch; found   : Array[String]  required: Array[Any]

We could fix the above error in the following manner:

def getLength[T](x: Array[T]): Int = x.length

getLength(stringArray)

Do you realize the potential overhead of the above fix? We’ve parameterized the method, but now we have a superfluous type parameter in our method. Speaking precisely, I mean I want an Array, and I don’t care what type of things it contains. This verbosity of providing a type parameter is a hassle sometimes.

Having this basic understanding of the normal variable declaration, let us try to understand existential types. By Definition “Existential types are a way of abstracting over types. They let you “acknowledge” that there is a type involved without specifying exactly what it is, usually because you don’t know what it is and you don’t need that knowledge in the current context.” Existential types are normal type variables, except that the variable only shows up on the RHS of the declaration.

type F = SomeClass[A] forSome { type A }

Let us take an example:

sealed trait F

final case class SomeClass[A](a: A) extends F

case class User(name: String, age: Int, contact: String)

SomeClass("SomeString"): F
SomeClass(1: Int): F
SomeClass(User): F

Notice that `A` appears only on the right in case of existential type. The advantage of this is that the final type, F, will not change regardless of the type of A.

Let us try to fit in the existential type in the getLength() method defined above as well.

def getLength(x : Array[T] forSome { type T}): Int = x.length

Let us expand a little more with another example:

sealed trait Existential {
   type Inner
   val value: Inner
}

final case class PrepareExistential[A](value: A) extends Existential {
  type Inner = A
}

PrepareExistential("SomeText"): Existential
PrepareExistential(1: Int): Existential
PrepareExistential(User): Existential

Notice that the PrepareExistential is a type eraser. The fact is irrelevant to the data type we put into PrepareExistential — it will erase the type and always return Existential. Let us take this a step further. The next logical line of questions is, “If we have some function that returns and existential then what shall be the type of inner? ”

The simplest answer would be “We don’t know.” I would, in my defense, say that the original type defined in PrepareExistential has been erased from the compilation. But that is incorrect. This doesn’t imply that we have lost all the information. We know for a fact is exists. Hence this is called existential type.

Another inevitable question that follows is “Where should we use existential types then?” But before I answer this question, there is another question “What is the use of type erasures?” To answer that, let me quote an answer from Martin Odersky himself: “Scala uses the erasure model of generics, just like Java, so we don’t see the type parameters anymore when programs are run. We have to do erasure because we need to interoperate with Java. But then what happens when we do reflection or want to express what goes on the in the VM? We need to be able to represent what the JVM does using the types we have in Scala, and existential types let us do that.”

Existential types have an important property of unifying different types into a single one with shared restrictions. These restrictions could be anything: from upper bounds to type classes or even a combination.  A very common use case is the creation of type-safe wrappers around unsafe libraries. Consider the following:

def write(objs: Object*): String

The signature of the above function is not special, it is very generic. Also, since the object will probably take everything, the program shall crash at runtime rather than failing at compile time. In the context of Scala specifically, a lot of these Java libraries have these generic methods and interfaces wherein certain Scala types don’t work, like BigInt, Int, List etc.

So if we can think of an Object as an existential type, we could resolve the problem of the type being too wide of encompassing all types. Here in, we need to restrict the number of types that are workable with the write. Let us improvise

def safeWrite(columns: AnyAllowedType*): String = {
    write(columns.map(_.toObject):_*)
}

Let us extend the getLength example:

def getLength(x : Array[T] forSome { type T <: CharSequence}) = 
 x.foreach(y => println(y.length))

Notice the additional restriction we have imposed. Here, we wanted to act on a more specific type, but did not care exactly what type it was.  The type arguments for an existential type can declare upper and lower bounds just like normal type declarations. By adding bounds, all we have done is restrict the range of T. An Array[Int] is not an Array[T] forSome { type T <: CharSequence }

In a generic definition, for a type T, M[T] is a type, but M is not itself a type. M could be List, Array, Class, etc. M[T] forSome { type T; } is the type of all things for which there is some T such that they are of type M[T]. So an Array[String] is of this type because we can choose T = String.

Before concluding the blog, it is essential to address one last question, “Are existential types the same as raw types?” A simple answer is NO.  Existential types are not raw types. Another important thing to understand is that existentials are safe, raw types are not. In Scala, type arguments are always required. The common problem Scala developers often face is that they are unable to implement some Java method with missing type arguments in its signature, e.g. one that takes a raw List as an argument.

Example: Consider using the following Java code:

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

abstract class TestExistential {
    static List arrayOfWords() {
        return new ArrayList<>(Arrays.asList("hi", "Welcome", "to", "Knoldus"));
    }
}

class UnsafeTypes extends TestExistential {
   public static final List wordsRaw = arrayOfWords();
}

warning: [rawtypes] found raw type: List missing type arguments for generic class List where E is a type-variable: E extends Object declared in interface List

class ExistentialTypes extends TestExistential {
    public static final List<?> wordsExistentialType = arrayOfWords();
}

Notice the warning here in the UnsafeTypes, whereas while using the same in Scala, there is no warning for the equivalent to wordsRaw, as types are inferred and are type safe. If you get a Java raw type, such as java.util.List, it is a list where you don’t know the element type. This can be represented in Scala by an existential type:

val stringArray: util.List[String] = TestExistential.arrayOfWords()

val genericArray: util.List[_] = TestExistential.arrayOfWords()

In essence, the reason that existential is safe is that the rules in place for values of existential type are consistent with the rest of the generic system, whereas raw types contradict those rules, resulting in code that is not type check.

From a developer’s perspective, existential types are quite powerful when mixed with the correct restrictions. They prove to be potent for the following scenarios:

• We need to make some sense of Java’s wildcards, and existential types are the sense we make of them.
• We need to make some sense of Java’s raw types because they are also still in the libraries, the un-generic types.
• We need existential types as a way to explain what goes on in the VM at the high level of Scala.