Chapter 17. Type Parameters
Topics in This Chapter L2
In Scala, you can use type parameters to implement classes and functions that work with multiple types. For example, an Array[T] stores elements of an arbitrary type T. The basic idea is very simple, but the details can get tricky. Sometimes, you need to place restrictions on the type. For example, to sort elements, T must provide an ordering. Furthermore, if the parameter type varies, what should happen with the parameterized type? For example, can you pass an Array[String] to a function that expects an Array[Any]? In Scala, you specify how your types should vary depending on their parameters.
The key points of this chapter are:
Classes, traits, methods, and functions can have type parameters.
Place the type parameters after the name, enclosed in square brackets.
Type bounds have the form
T <: UpperBound,T >: LowerBound,T : ContextBound.You can restrict a method with a type constraint such as
(given ev: T <:< UpperBound).Use
+T(covariance) to indicate that a generic type’s subtype relationship is in the same direction as the parameterT, or-T(contravariance) to indicate the reverse direction.Covariance is appropriate for parameters that denote outputs, such as elements in an immutable collection.
Contravariance is appropriate for parameters that denote inputs, such as function parameters.
17.1 Generic Classes
As in Java or C++, classes and traits can have type parameters. In Scala, you use square brackets for type parameters, for example:
class Pair[T, S](val first: T, val second: S)This defines a class with two type parameters T and S. You use the type parameters in the class definition to define the types of variables, method parameters, and return values.
A class with one or more type parameters is generic. If you substitute actual types for the type parameters, you get an ordinary class, such as Pair[Int, String].
Pleasantly, Scala attempts to infer the actual types from the construction parameters:
val p = Pair(42, "String") // It's a Pair[Int, String]You can also specify the types yourself:
val p2 = Pair[Any, Any](42, "String")
Note
Of course, Scala has a pair type (T, S), so there is no actual need for a Pair[T, S] class. However, this class and its variations provide a convenient example for discussing the finer points of type parameters.
Note
You can write any generic type with two type parameters in infix notation, such as Double Map String instead of Map[Double, String].
If you have such a type, you can annotate it as + to modify how it is displayed in compiler and REPL messages. For example, if you define
@showAsInfix class x[T, U](val first: T, val second: U)then the type x[String, Int] is displayed as String x Int.
17.2 Generic Functions
Functions and methods can also have type parameters. Here is a simple example:
def getMiddle[T](a: Array[T]) = a(a.length / 2)As with generic classes, you place the type parameter after the name.
Scala infers the actual types from the arguments in the call.
getMiddle(Array("Mary", "had", "a", "little", "lamb")) // Calls getMiddle[String]If you need to, you can specify the type:
val f = getMiddle[String] // The function, saved in f17.3 Bounds for Type Variables
Sometimes, you need to place restrictions on type variables. Consider a generic Pair where both components have the same type, like this:
class Pair[T](val first: T, val second: T)Now we want to add a method that produces the smaller value:
class Pair[T](val first: T, val second: T) :def smaller = if first.compareTo(second) < 0 then first else second //Error
That’s wrong—we don’t know if first has a compareTo method. To solve this, we can add an upper bound T <: Comparable[T].
class Pair[T <: Comparable[T]](val first: T, val second: T) :
def smaller = if first.compareTo(second) < 0 then first else secondThis means that T must be a subtype of Comparable[T].
Now we can instantiate Pair[java.lang.String] but not Pair[java.net.URL], since String is a subtype of Comparable[String] but URL does not implement Comparable[URL]. For example:
val p = Pair("Fred", "Brooks")p.smaller //"Brooks"
Note
In this chapter, I use the Comparable type from Java in several examples. In Scala, it is more common to use the Ordering trait. See the next section for details.
CAUTION
If you construct a Pair(4, 2), you will get a Pair[java.lang.Integer] since the Scala Int type does not extend the java.util.Comparable.
You can also specify a lower bound for a type. For example, suppose we want to define a method that replaces the first component of a pair with another value. Our pairs are immutable, so we need to return a new pair. Here is a first attempt:
class Pair[T](val first: T, val second: T) :
def replaceFirst(newFirst: T) = Pair[T](newFirst, second)But we can do better than that. Suppose we have a Pair[Student] and want to replace the first component with a Person. Of course, then the result must be a Pair[Person]. In general, the replacement type must be a supertype of the pair’s component type. Use the >: symbol for the supertype relationship:
def replaceFirst[R >: T](newFirst: R) = Pair[R](newFirst, second) CAUTION
The supertype relationship symbol is >:, even though :> would be more symmetrical. This is analogous to the <= and >= operators.
The example uses the type parameter in the returned pair for greater clarity. You can also write
def replaceFirst[R >: T](newFirst: R) = Pair(newFirst, second)Then the return type is correctly inferred as Pair[R].
CAUTION
If you omit the lower bound,
def replaceFirst[R](newFirst: R) = Pair(newFirst, second)the method will compile, but it will return a Pair[Any].
17.4 Context Bounds
A context bound has the form T : M, where M is another generic type with a single type parameter. It requires that there is a “given value” of type M[T]. The type M[T] need not be a sub- or supertype of T. We discuss given values in detail in Chapter 19.
For example,
class Pair[T : Ordering]requires that there is a given value of type Ordering[T]. You can "summon" that given value when it is needed in the methods of the class. Here is an example:
class Pair[T : Ordering](val first: T, val second: T) :
def smaller =
if summon[Ordering[T]].compare(first, second) < 0 then first else secondA type parameter can have upper or lower bounds together with context bounds. In that case, the context bounds come last:
class Pair[T <: Serializable : Ordering]17.5 The ClassTag Context Bound
To instantiate a generic Array[T], one needs a ClassTag[T] object. This is required for primitive type arrays to work correctly. For example, if T is Int, you want an int[] array in the virtual machine. If you write a generic function that constructs a generic array, you need to help it out and pass that class tag object. Use a context bound, like this:
import scala.reflect.*
def makePair[T : ClassTag](first: T, second: T) =
Array[T](first, second)If you call makePair(4, 9), the compiler locates the given ClassTag[Int] instance and actually calls makePair(4, 9)(classTag). Then the Array constructor is translated to a call classTag.newArray, which in the case of a ClassTag[Int] constructs a primitive array of type int[].
Why all this complexity? In the virtual machine, generic types are erased. There is only a single makePair method that needs to work for all types T.
17.6 Multiple Bounds
A type variable can have both an upper and a lower bound. The syntax is this:
T >: Lower <: UpperYou can’t have multiple upper or lower bounds. However, you can still require that a type implements multiple traits, like this:
T <: Comparable[T] & Serializable & CloneableYou can have more than one context bound:
T : Ordering : ClassTag17.7 Type Constraints L3
Type constraints give you another way of restricting types. There are two relationships that you can use:
T <:< U
T =:= UThese constraints test whether T is a subtype of U or whether T and U are the same type. To use such a constraint, add a “using parameter” like this:
class Pair[T](val first: T, val second: T)(using ev: T <:< Comparable[T]) :
def smaller = if first.compareTo(second) < 0 then first else second Note
See Chapter 19 for an explanation of the syntax, and for an analysis of the inner workings of the type constraints.
In the example above, there is no advantage to using a type constraint over a type bound class Pair[T <: Comparable[T]]. However, type constraints give you more control in specialized circumstances.
In particular, type constraints let you supply a method in a generic class that only makes sense for some types. Here is an example:
class Pair[T](val first: T, val second: T) :
def smaller(using ev: T <:< Comparable[T]) =
if first.compareTo(second) < 0 then first else secondYou can form a Pair[URL], even though URL is not a subtype of Comparable[URL]. You will get an error only if you invoke the smaller method.
The orNull method in the Option class also uses a type constraint. Here is how to use the method:
val friends = Map("Fred" -> "Barney", ...)val friendOpt = friends.get("Wilma") //An Option[String]val friendOrNull = friendOpt.orNull //A String or null
The orNull method can be useful when working with Java code where it is common to encode missing values as null.
But now consider this code:
val numberOpt = if scala.math.random() < 0.5 then Some(42) else Noneval number: Int = numberOpt.orNull //Error
The second line should not be legal. After all, the Int type doesn’t have null as a valid value. For that reason, orNull is implemented using a constraint Null <:< A. You can instantiate Option[Int], so long as you stay away from orNull for those instances.
See Exercise 8 on page 274 for another example with the =:= constraint.
17.8 Variance
Suppose we have a function that does something with a Pair[Person]:
def makeFriends(p: Pair[Person]) = ...If Student is a subclass of Person, can I call makeFriend with a Pair[Student]? By default, this is an error. Even though Student is a subtype of Person, there is no relationship between Pair[Student] and Pair[Person].
If you want such a relationship, you have to indicate it when you define the Pair class:
class Pair[+T](val first: T, val second: T)The + means that the type is covariant in T—that is, it varies in the same direction. Since Student is a subtype of Person, a Pair[Student] is now a subtype of Pair[Person].
It is also possible to have variance in the other direction. Consider a generic type Friend[T], which denotes someone who is willing to befriend anyone of type T.
trait Friend[T] :
def befriend(someone: T): StringNow suppose you have a function
def makeFriendWith(s: Student, f: Friend[Student]) = f.befriend(s)Can you call it with a Friend[Person]? That is, if you have
class Person(name: String) extends Friend[Person] :
override def toString = s"Person $name"
override def befriend(someone: Person) = s"$this and $someone are now friends"
class Student(name: String, major: String) extends Person(name) :
override def toString = s"Student $name majoring in $major"
val susan = Student("Susan", "CS")
val fred = Person("Fred")will the call makeFriendWith(susan, fred) succeed? It seems like it should. If Fred is willing to befriend any person, he’ll surely like to be friends with Susan.
Note that the type varies in the opposite direction of the subtype relationship. Student is a subtype of Person, but Friend[Student] needs to be a supertype of Friend[Person]. In that case, you declare the type parameter to be contravariant:
trait Friend[-T] :
def befriend(someone: T): StringYou can have both variance types in a single generic type. For example, functions with a single parameter have the type Function1[-A, +R]. To see why these are the appropriate variances, consider a function
def friendsOfStudents(students: Seq[Student],
findFriend: Function1[Student, Person]) =
// You can write the second parameter as findFriend: Student => Person
for s <- students yield findFriend(s)Suppose you have a function
def findStudentFriendsOfPerson(p: Person): Student = ...Can you call friendsOfStudents with that function? Of course you can. It’s willing to take any person, so surely it will take a Student. That’s contravariance in the first type parameter of Function1. It yields Student results, which can be put into a collection of Person objects. The second type parameter is covariant.
17.9 Co- and Contravariant Positions
In the preceding section, you saw that functions are contravariant in their arguments and covariant in their results. Generally, it makes sense to use contravariance for the values an object consumes, and covariance for the values it produces. (Aide-mémoire: contravariance consumes.)
If an object does both, then the type should be left invariant. This is generally the case for mutable data structures. For example, in Scala, arrays are invariant. You can’t convert an Array[Student] to an Array[Person] or the other way around. This would not be safe. Consider the following:
val students = Array.ofDim[Student](length)val people: Array[Person] = students //Not legal, but suppose it was...people(0) = Person("Fred") //Oh no! Now students(0) isn’t a Student
Conversely,
val people: Array[Person] = Array(Person("Fred"))val students: Array[Student] = people //Not legal, but suppose it was...val firstStudent: Student = students(0) //Oh no! Now firstStudent isn’t a Student
Note
In Java, it is possible to convert a Student[] array to a Person[] array, but if you try to add a nonstudent into such an array, an ArrayStoreException is thrown. In Scala, the compiler rejects programs that could cause type errors.
Note
The IArray[+T] class is a wrapper for immutable JVM arrays. Note that the element type is covariant.
Suppose we tried to declare a covariant mutable pair. This wouldn’t work. It would be like an array with two elements, and one could produce the same kind of error that you just saw.
To find such an error, the Scala compiler uses a simple rule for variance checking. Each type parameter is assigned a position, either covariant or contravariant, which must match its actual variance. Parameters are contravariant positions, and return types are covariant. For example, in the declaration
class Pair[+T](var first: T, var second: T) // Erroryou get an error complaining that the covariant type T occurs in a contravariant position in the setter
first_=(value: T)Inside a function parameter, the variance flips—its parameters are covariant. For example, look at the foldLeft method of Iterable[+A]:
foldLeft[B](z: B)(op: (B, A) => B): B
- + + - +Note that A is in a covariant position, which is permissible given the +A type parameter. However, B is in both co- and contravariant positions. That too is OK since it was declared as an invariant type parameter.
These position rules are simple and safe, but they sometimes get in the way. Consider the replaceFirst method from Section 17.3, “Bounds for Type Variables,” on page 265 in an immutable pair:
class Pair[+T](val first: T, val second: T) :def replaceFirst(newFirst: T) = Pair[T](newFirst, second) //Error
The compiler rejects this, because the parameter type T is in a contravariant position. Yet this method cannot damage the pair—it returns a new pair.
The remedy is to come up with a second type parameter for the method, like this:
def replaceFirst[R >: T](newFirst: R) = Pair[R](newFirst, second)Now the method is a generic method with another type parameter R. But R is invariant, so it doesn’t matter that it appears in a contravariant position.
17.10 Objects Can’t Be Generic
It is not possible to add type parameters to objects. Consider, for example, immutable lists. A list with element type T is either empty, or it has a head of type T and a tail of type List[T]:
abstract sealed class List[+T] :
def isEmpty: Boolean
def head: T
def tail: List[T]
def toString = if isEmpty then "" else s"$head $tail"
case class NonEmpty[T](head: T, tail: List[T]) extends List[T] :
def isEmpty = false
case class Empty[T] extends List[T] :
def isEmpty = true
def head = throw UnsupportedOperationException()
def tail = throw UnsupportedOperationException() Note
Here I use NonEmpty and Empty for clarity. They correspond to :: and Nil in Scala lists.
It seems silly to define Empty as a class. It has no state. But you can’t simply turn it into an object:
case object Empty[T] extends List[T] : // ErrorYou can’t add a type parameter to an object. In this case, a remedy is to inherit List[Nothing]:
case object Empty extends List[Nothing] :Recall from Chapter 8 that the Nothing type is a subtype of all types. Thus, when we make a one-element list
val lst = NonEmpty(42, Empty)type checking is successful. Due to covariance, a List[Nothing] is convertible into a List[Int], and the NonEmpty[Int] constructor can be invoked.
17.11 Wildcards
In Java, all generic types are invariant. However, you can vary the types where you use them, using wildcards. For example, a method
void makeFriends(List<? extends Person> people) // This is Javacan be called with a List<Student>.
You can use wildcards in Scala too. They look like this:
def makeFriends(people: java.util.List[? <: Person]) = ... // This is ScalaIn Scala, you don’t need the wildcard for a covariant Pair class. But suppose Pair is invariant:
class Pair[T](var first: T, var second: T)Then you can define
def makeFriends(p: Pair[? <: Person]) = ... // OK to call with a Pair[Student]You can also use wildcards for contravariance:
import java.util.Comparator
def min[T](p: Pair[T], comp: Comparator[? >: T]) =
if comp.compare(p.first, p.second) < 0 then p.first else p.secondIf necessary, you can have both variances. Here T must be a subtype of Comparable[U], where U (the parameter of the compare method) must be a supertype of T, so that it can accept a value of type T:
def min[T <: Comparable[? >: T]](p: Pair[T]) =
if p.first.compareTo(p.second) < 0 then p.first else p.second17.12 Polymorphic Functions
Consider this top-level function declaration:
def firstLast[T](a: Array[T]) = (a(0), a(a.length - 1))In Chapter 12, you saw how to rewrite a def into a val and a lambda expression:
val firstLast = (a: Array[T]) => ...But that can’t be quite right. You need to put the type parameter somewhere. You can’t put it with firstLast—there are no generic val:
val firstLast[T] = (a: Array[T]) => (a(0), a(a.length - 1)) // ErrorInstead, you should think of firstLast to have two curried parameters: the type T and the array a. Here is the correct syntax:
val firstLast = [T] => (a: Array[T]) => (a(0), a(a.length - 1))The type of firstLast is
[T] => Array[T] => (T, T)Such a type is called a polymorphic function type.
Note that firstLast[String] is an ordinary function with type Array[String] => (String, String). The type parameter has been “curried.”
Polymorphic functions are useful when you need a lambda that must work with different types. Suppose you want to wrap all elements of a tuple in Some, transforming (1, 3.14, "Fred") into (Some(1), Some(3.14), Some("Fred")).
There is a Tuple.map method for just this purpose. The function to be mapped requires a type parameter since each element can have a different type. Here is how to do it:
val tuple = (1, 3.14, "Fred")
tuple.map([T] => (x: T) => Some(x))The type of that lambda expression is [T] => T => Some[T].
CAUTION
In Chapter 20, you will encounter type lambdas such as [X] =>> Some[X]. They look similar but are completely different. A type lambda is a type-level function. It consumes a type and produces another. In contrast, a polymorphic function type is a type.
Exercises
1. Define an immutable class Pair[T, S] with a method swap that returns a new pair with the components swapped.
2. Define a mutable class Pair[T] with a method swap that swaps the components of the pair.
3. Given a class Pair[T, S], write a generic method swap that takes a pair as its argument and returns a new pair with the components swapped.
4. Why don’t we need a lower bound for the replaceFirst method in Section 17.3, “Bounds for Type Variables,” on page 265 if we want to replace the first component of a Pair[Person] with a Student?
5. Why does RichInt implement Comparable[Int] and not Comparable[RichInt]?
6. Write a generic method middle that returns the middle element from any Iterable[T]. For example, middle("World") is 'r'.
7. Add a method zip to the Pair[T] class that zips a pair of pairs:
val p = Pair(Pair(1, 2), Pair(3, 4))
p.zip // Pair(Pair(1, 3), Pair(2, 4))Of course, this method can only be applied if T is itself a Pair type. Use a type constraint.
8. Write a class Pair[T, S] that implements a mutable pair. Using the =:= type constraint, provide a swap method that swaps the components in place, provided that S and T are the same type. Demonstrate that you can invoke swap on Pair("Fred", "Brooks") and that you can construct Pair("Fred", 42) but you cannot invoke swap on it.
9. Look through the methods of the Iterable[+A] trait. Which methods use the type parameter A? Why is it in a covariant position in these methods?
10. In Section 17.9, “Co- and Contravariant Positions,” on page 270, the replaceFirst method has a type bound. Why can’t you define an equivalent method on a mutable Pair[T]?
def replaceFirst[R >: T](newFirst: R) =first = newFirst //Error
11. It may seem strange to restrict method parameters in an immutable class Pair[+T]. However, suppose you could define
def replaceFirst(newFirst: T)in a Pair[+T]. The problem is that this method can be overridden in an unsound way. Construct an example of the problem. Define a subclass NastyDoublePair of Pair[Double] that overrides replaceFirst so that it makes a pair with the square root of newFirst. Then consider the call replaceFirst("Hello") on a Pair[Any] that is actually a NastyDoublePair.