Scala has a unified type system. What this means is that all types, including "primitive" types, inherit from a common type. Any is a supertype of all types. It is often called the top type, and defines universal methods such as equals, hashCode, and toString. Nothing is a subtype of all types, and is often called the bottom type. There is no value that has a type of Nothing, so a common use case for it is to signal non-termination: a thrown exception, a program exit, or an infinite loop.

Any has two direct subclasses: AnyVal and AnyRef. Value types are represented by AnyVal. AnyRef represents the reference types. There are nine non-nullable predefined value types: Double, Float, Long, Boolean, Unit, Byte, Char, Short, and Int. All of these types are similar in other programming languages, except Unit. There is one instance of Unit, which is declared like (). Unit is an important return type as all the functions in Scala must return something. All non-value types are defined as reference types. Every user-defined type in Scala is a subtype of AnyRef. Comparing AnyRef to a Java runtime environment, AnyRef is similar to java.lang.Object.

Null is a subtype of all reference types. It contains a single value identified by the literal null. Null is used for operating between other programming languages but it is not recommended to use it in Scala. Scala provides other safer options to null, which we shall cover later in the chapter.

Parametric polymorphism is what allows you to write generic code for values of different types without losing the advantages of static typing.

Without polymorphism, a generic list type structure would always look like this:

scala> 2 :: 1 :: "bar" :: "foo" :: Nil
res0: List[Any] = List(2, 1, bar, foo)

Having to deal with the Any type in these cases means that we can't recover any type information about the individual members:

scala> res0.head
res1: Any = 2

Without polymorphism, we would be forced to use casts and thus would lack type safety (since casts are dynamic and happen at runtime).

Scala enables polymorphism through the specification of type variables, which you probably already came across when implementing generic functions:

scala> def drop1[A](l: List[A]) = l.tail
drop1: [A](l: List[A])List[A]

scala> drop1(List(1, 2, 3))
res1: List[Int] = List(2, 3)

A common problem of statically typed languages is that they provide too much "syntactic overhead". Scala rectifies this issue by introducing type interface. In Scala, type inference is local and it will consider one expression at a time.

Type inference reduces the need for most type annotations. For example, declaring the type of variable is not necessary in Scala, as the compiler can identify the type from the initialization expression. Return types of methods are also successfully identified by the compiler, as they resemble to the body type:

val x = 3 + 4 * 5         // the type of x is Int
val y = x.toString()      // the type of y is String
def succ(x: Int) = x + 2  // method succ returns Int values

The compiler is not able to infer a result type from recursive methods, though. The following declaration will not compile:

def fac(n: Int) = if (n == 0) 1 else n * fac(n - 1)

The error message is enough to identify the issue:

<console>:11: error: recursive method fac needs result type
       def fac(n: Int) = if (n == 0) 1 else n * fac(n - 1)

Parameterized types are the same as generic types in Java. A generic type is a generic class or interface that is parameterized over types. For example:

class Stack[T] {
  var elems: List[T] = Nil
  def push(x: T) { elems = x :: elems }
  def top: T = elems.head
  def pop() {elems = elems.tail }
}

Generic types can interact with type checking using bounds or variance. We'll cover variance in the next section.

Scala allows programmers to restrict polymorphic variables using bounds. These bounds express subtype ( <:) or supertype ( :>) relationships. For example, if we've defined our drop1 method before as the following:

scala> def drop1[A <: AnyRef](l: List[A]) = l.tail
drop1: [A <: AnyRef](l: List[A])List[A]

The following wouldn't compile:

scala> drop1(List(1, 2, 3))
<console>:13: error: inferred type arguments [Int] do not conform to method drop1's type parameter bounds [A <: AnyRef]
       drop1(List(1, 2, 3))
       ^
<console>:13: error: type mismatch;
 found   : List[Int]
 required: List[A]
       drop1(List(1, 2, 3))

An existential type in Scala is a type with some unknown parts in it. For example:

Foo[T] forSome { type T }

An existential type includes references to type members that we know exist, but whose concrete values we don't care about. In the preceding code, T is a type we don't know concretely, but that we know exists. Using existential types, we can leave some parts of your program unknown, and still typecheck it with different implementations for those unknown parts.

Imagine that you have the following method:

scala> def foo(x: Array[Any]) = x.length
foo: (x: Array[Any])Int

If you try the following, it won't compile, because an Array[String] is not an Array[Any] (will see why in the next section):

scala> val a = Array("foo", "bar", "baz")
a: Array[String] = Array(foo, bar, baz)

scala> foo(a)
<console>:14: error: type mismatch;
 found   : Array[String]
 required: Array[Any]
We can fix this by adding a type parameter:
scala> def foo[T](x: Array[T]) = x.length
foo: [T](x: Array[T])Int
scala> foo(a)
res0: Int = 3

Now, foo is parameterized to accept any T. But now we have to carry around this type parameter, and we only care about methods on Array and not what the Array contains. We can therefore use existential types to get around this.

scala> def foo(x: Array[T] forSome { type T }) = x.length
foo: (x: Array[_])Int

scala> foo(a)
res0: Int = 3

This pattern is common, so Scala provides us with "wildcards" for when we don't want to name a type variable:

scala> def foo(x: Array[_]) = x.length
foo: (x: Array[_])Int

scala> foo(a)
res0: Int = 3

In this activity, we'll be generalizing an implementation of a binary search tree. Let's assume you have the following definition for a binary search tree of integers. We want to generalize our implementation of a binary search tree from an IntTree to a Tree[A]. Perform the necessary modifications to the code to support the new definition and also have the insert and search methods work on the new definition. You may need to modify the insert and search definitions to provide a generic comparison function. We would like to use this new generic data structure to store information about the users that visit our website, which are being modeled as the User(username: String, country: String) case class:

trait IntTree
case class IntNode(value: Int, left: IntTree, right: IntTree) extends IntTree
case object IntEmpty extends IntTree

The previous definition supports these methods:

def insert(value: Int, tree: IntTree): IntTree =
  tree match {
    case IntEmpty => IntNode(value, IntEmpty, IntEmpty)
    case IntNode(currentValue, left, right) =>
      if (value < currentValue)
        IntNode(currentValue, insert(value, left), right)
      else
        IntNode(currentValue, left, insert(value, right))
  }

def search(value: Int, tree: IntTree): Boolean =
  tree match {
    case IntEmpty => false
    case IntNode(currentValue, left, right) =>
      value == currentValue ||
        (value < currentValue && search(value, left)) ||
       (value >= currentValue && search(value, right))
  }

In this section, we covered the unified type system of Scala and how Scala achieves polymorphism. We also introduced type inference and the basic rules of when it's applied. Bounds were also introduced as a convenient way to restrict polymorphic types.