Chapter 12. The Scala Type System

Scala is a statically-typed language. Its type system is one of the most sophisticated in any programming language, in part because it combines comprehensive ideas from functional programming and object-oriented programming. The type system tries to be logically comprehensive, complete, and consistent. It exceeds limitations in Java’s type system while containing innovations which appear in Scala for the first time.

3 comments

  1. Alex Cruise Posted 1 month, 10 days and 11 hours ago

    "Its" type system. :)

  2. Alex Cruise Posted 1 month, 10 days and 11 hours ago

    Suggest "... because it comprehensively combines ..."

  3. Dean Wampler Posted 1 month, 10 days and 5 hours ago

    Fixed the "its". Will consider the 2nd comment. thx.

Add a comment

However, the type system can be intimidating at first, especially if you come from a dynamically-typed language like Ruby or Python. Fortunately, type inference hides most of the complexities away. Most of the time, you don’t need to know the particulars, so we encourage you not to worry that you must master the type system in order to use Scala effectively. You might choose to skim this chapter if you’re new to Scala, so you’ll know where to look when type-related questions arise later.

No comments yet

Still, the more you know about the type system, the more you will be able to exploit its features in your programs. This is especially true for library writers, who will want to understand when to use parameterized types vs. abstract types, which type parameters should be covariant, contravariant, or invariant under subtyping, and so forth. Also, some understanding of the type system will help you understand and debug the occasional compilation failure related to typing. Finally, this understanding will help you make sense of the type information shown in the sources and Scaladocs for Scala libraries.

No comments yet

If you didn’t understand some of the terms we used in the preceding paragraphs, don’t worry. We’ll explain them and why they are useful. We’re not going to discuss Scala’s type system in exhaustive detail. Rather, we want you to come away with a pragmatic understanding of the type system. You should develop an awareness of the features available, what purposes they serve, and how to read and understand type declarations.

No comments yet

We’ll also highlight similarities with Java’s type system, since it may be a familiar point of reference for you. Understanding the differences is also useful for interoperability with Java libraries. To focus the discussion, we won’t cover the .NET type system, except to point out some notable differences that .NET programmers will want to know.

No comments yet

Reflecting on Types

Scala supports the same reflection capabilities that Java and .NET support. The syntax is different in some cases.

First, you can use the same methods you might use in Java or .NET code. The following script shows some of the reflection methods available on the JVM, through java.lang.Object and java.lang.Class.

// code-examples/TypeSystem/reflection/jvm-script.scala

trait T[A] {
  val vT: A
  def mT = vT
}

class C extends T[String] {
  val vT = "T"
  val vC = "C"
  def mC = vC

  class C2
  trait T2
}

val c = new C
val clazz = c.getClass              // method from java.lang.Object
val clazz2 = classOf[C]             // Scala method: classOf[C] ~ C.class
val methods = clazz.getMethods      // method from java.lang.Class<T>
val ctors = clazz.getConstructors   // ...
val fields = clazz.getFields
val annos = clazz.getAnnotations
val name  = clazz.getName
val parentInterfaces = clazz.getInterfaces
val superClass = clazz.getSuperclass
val typeParams = clazz.getTypeParameters

Note that these methods are only available on subtypes of AnyRef.

2 comments

  1. Matt Hellige Posted 1 month, 11 days and 6 hours ago

    Actually isn't it rather that classOf[C] == C.class?

  2. Dean Wampler Posted 1 month, 10 days and 12 hours ago

    That's probably true, although "C.class" won't compile in Scala. What I just noticed however, is that classOf[C] and c.getClass return slightly different things: scala> classOf[C] res0: java.lang.Class[C] = class C

    scala> c.getClass res1: java.lang.Class[_] = class C

    scala> C.class :1: error: identifier expected but 'class' found. C.class

    Will need to comment that...

Add a comment

The classOf[T] method returns the runtime representation for a Scala type. It is analogous to the Java expression T.class. Using classOf[T] is convenient when you have a type that you want information about, while getClass is convenient for retrieving the same information from an instance of the type.

However, classOf[T] and getClass return slightly different values, reflecting the effect of type erasure on the JVM, in the case of getClass.

scala> classOf[C]
res0: java.lang.Class[C] = class C

scala> c.getClass
res1: java.lang.Class[_] = class C

Note

Although .NET does not have type erasure, meaning it supports reified types, the .NET version of Scala currently follows the JVM’s erasure model in order to avoid incompatibilities that would require a “forked” implementation.

We’ll discuss a workaround for erasure, called Manifests, after we discuss Parameterized Types in the next section.

Scala also provides methods for testing whether or not an object matches a type and also for casting an object to a type.

x.isInstanceOf[T] will return true if the instance x is of type T. However, this test is subject to type erasure. For example, List(3.14159).isInstanceOf[List[String]] will return true, because the type parameter of List is lost at the byte code level. However, you’ll get an “unchecked” warning from the compiler.

2 comments

  1. Matt Hellige Posted 1 month, 11 days and 6 hours ago

    Maybe worth mentioning that it will also issue a warning...

  2. Dean Wampler Posted 1 month, 10 days and 12 hours ago

    Good idea. will add...

Add a comment

x.asInstanceOf[T] will cast x to T or throw a ClassCastException if T and the type of x are not compatible. Once again, type erasure must be considered with parameterized types. The expression List(3.14159).asInstanceOf[List[String]] will succeed.

Note that these two operations are methods and not keywords in the language, and their names are deliberately somewhat verbose. Normally, type checks and casts like these should be avoided. For type checks, use pattern matching instead. For casts, consider why a cast is necessary and determine if a refactoring of the design can eliminate the requirement for a cast.

Note

At the time of this writing, there are some experimental features that might appear in the final version 2.8 release in the scala.reflect package. These features are designed to make reflective examination and invocation of code easier than using the corresponding Java methods.

Understanding Parameterized Types

We introduced parameterized types and methods in Chapter 1, Zero to Sixty: Introducing Scala, and filled in a few more details in the section called “Abstract Types And Parameterized Types” in Chapter 2, Type Less, Do More. If you come from a Java or C# background, you probably already have some knowledge of parameterized types and methods. Now we explore the details of Scala’s sophisticated support for parameterized types.

Scala’s parameterized types are similar to Java and C# generics and C++ templates. They provide the same capabilities as Java generics, but with significant differences and extensions, reflecting the sophistication of Scala’s type system.

To recap, a declaration like class List[+A] means that List is parameterized by a single type, represented by A. The ‘+’ is called a variance annotation. We’ll come back to it in the section called “Variance Under Inheritance” below.

Sometimes, a parameterized type like List is called a type constructor, because it is used to create specific types. For example, List is the type constructor for List[String] and List[Int], which are different types. (Although they are actually implemented with the same byte code due to type erasure.) In fact, it’s more accurate to say that all traits and classes are type constructors. Those without type parameters are effectively zero-argument, parameterized types.

2 comments

  1. Matt Hellige Posted 1 month, 11 days and 6 hours ago

    This terminology seems off to me. I would instead say that "List" is a type constructor, because it is used to create specific types. I don't know of any specific jargon for a declaration like "List[+A]", it's just a regular type declaration that happens to declare a type with an argument.

    In fact, technically, Int is usually regarded as a type constructor as well, so I find this whole thing a little confused. In any case I don't think it matches standard usage. Feel free to email me if you like.

  2. Dean Wampler Posted 1 month, 10 days and 12 hours ago

    Will follow up with you. Not sure I agree, but I could be wrong. Has happened in the past ;)

Add a comment

Warning

If you write class StringList[String] extends List[String] {…}, Scala will interpret String as the name of the type parameter, not the creation of a type based on actual Strings. You want to write class StringList extends List[String] {…}.

Manifests

There is an experimental feature in Scala (since version 2.7.2), called Manifests, that captures type information that is erased in the byte code. This feature is not documented in the Scaladocs, but you can examine the source for the scala.reflect.Manifest trait. [Ortiz2008] discusses Manifests and provides examples of their use.

A Manifest is declared as an implicit argument to a method or type that wants to capture the erased type information. Unlike most implicit arguments, the user does not need to supply an in-scope Manifest value or method. Instead, the compiler generates one automatically. Here is an example the illustrates some of the strengths and weaknesses of Manifests.

// code-examples/TypeSystem/manifests/manifest-script.scala

import scala.reflect.Manifest

object WhichList {
  def apply[B](value: List[B])(implicit m: Manifest[B]) = m.toString match {
    case "int"              => println( "List[Int]" )
    case "double"           => println( "List[Double]" )
    case "java.lang.String" => println( "List[String]" )
    case _                  => println( "List[???]" )
  }
}

WhichList(List(1, 2, 3))
WhichList(List(1.1, 2.2, 3.3))
WhichList(List("one", "two", "three"))

List(List(1, 2, 3), List(1.1, 2.2, 3.3), List("one", "two", "three")) foreach {
  WhichList(_)
}

WhichList tries to determine the type of list passed in. It uses the value of the manifest’s toString method to determine this information. Notice that it works when the list is constructed inside the call to WhichList.apply. It does not work when a previously constructed list is passed to WhichList.apply.

The compiler exploits the type information it knows in the first case to construct the implicit Manifest with the correct B. However, when given previously-constructed lists, the crucial type information is already lost.

Hence, Manifests can’t “resurrect” type information from byte code, but they can be used capture and exploit type information before it is erased.

Parameterized Methods

Individual methods can also be parameterized. Good examples are the apply methods in companion objects for parameterized classes. Recall that companion objects are singleton objects associated with a companion class. There is only one instance of a singleton object, as its name implies, so type parameters would be meaningless.

Let’s consider object List, the companion object for class List[+A]. Here is the definition of the apply method in object List.

def apply[A](xs: A*): List[A] = xs.toList

The apply methods takes a variable length list of arguments of type A, which will be inferred from the arguments, and returns a list created from the arguments. Here is an example.

val languages = List("Scala", "Java", "Ruby", "C#", "C++", "Python", ...)
val positiveInts = List(1, 2, 3, 4, 5, 6, 7, ...)

We’ll look at other parameterized methods below.

Variance Under Inheritance

An important difference between Java and Scala generics is how variance under inheritance works. For example, if a method has an argument of type List[AnyRef], can you pass a List[String] value? In other words, should a List[String] be considered a subtype of List[AnyRef]. If so, this kind of variance is called covariance, because the supertype-subtype relationship of the container (the parameterized type) “goes in the same direction” as the relationship between the type parameters. In other contexts, you might want contravariant or invariant behavior, which we’ll describe shortly.

In Scala, the variance behavior is defined at the declaration site using variance annotations, ‘+’, ‘-’, or nothing. In other words, the type designer decides how the type should vary under inheritance.

Let’s examine the three kinds of variance, summarized in the following table, and understand how to use them effectively. We’ll assume that Tsup is a supertype of T and Tsub is a subtype of T.

Table 12.1. Type variance annotations and their meanings.

Annotation Java Equivalent Description

+

? extends T

Covariant subclassing. E.g., List[Tsub] is a subtype of List[T].

-

? super T

Contravariant subclassing. E.g., X[Tsup] is a subtype of X[T].

none

T

Invariant subclassing. E.g., Can’t substitute Y[Tsup] or Y[Tsub] for Y[T].


The “Java Equivalent” column is a bit misleading; we’ll explain why in a moment.

Class List is declared List[+A], which means that List[String] is a subclass of List[AnyRef], so Lists are covariant in the type parameter A. (When a type like List has only one covariant type parameter, you’ll often hear the shorthand expression “Lists are covariant” and similarly for types with a single contravariant type parameter.)

2 comments

  1. Matt Hellige Posted 1 month, 11 days and 5 hours ago

    I would explicitly state that it doesn't really make sense to say that a type by itself is co/contra-variant: it only makes sense to say that it is covariant with respect to a particular parameter. Then I'd note that sometimes we're sloppy for types with one parameter (like List) and we just say "List is covariant" rather than "List is covariant in its only parameter".

    I realize that it sounds stuffy and pedantic, but I think it's better to be clear and explicit: this stuff is confusing enough already!

  2. Dean Wampler Posted 1 month, 10 days and 12 hours ago

    Good point, and your right that the next example makes the point. Will clarify.

Add a comment

The traits FunctionN, for N equals 0 to 22, are used by Scala to implement function values as true objects. Let’s pick Function1 as a representative example. It is declared trait Function1[-T, +R].

1 comment

  1. Matt Hellige Posted 1 month, 11 days and 5 hours ago

    Example of my last comment. Given what you've said so far, I don't know what to say: is Function1 covariant or contravariant? I'm confused! Of course the answer is it's contravariant in T and covariant in R...

Add a comment

The +R is the return type and it has the covariant annotation ‘+’. The type for the single argument has the contravariant annotation ‘-’. For functions with more than one argument all the argument types have the contravariant annotation. So, for example, using our T, Tsup, and Tsub types, the following definition would be legal.

val f: Function1[T, T] = new Function1[Tsup, Tsub] { … }

Hence, the function traits are covariant in the return type parameter R and contravariant in the argument parameters T1, T2, …, TN.

So, what does this really mean? Let’s look at an example to understand the variance behavior. If you have prior experience with Design by Contract [DesignByContract], it might help you to recall how it works, which is very similar. (We will discuss Design by Contract briefly in the section called “Better Design with Design By Contract” in Chapter 13, Application Design.) This script demonstrates variance under inheritance.

// code-examples/TypeSystem/variances/func-script.scala
// WON'T COMPILE

class CSuper                { def msuper = println("CSuper") }
class C      extends CSuper { def m      = println("C") }
class CSub   extends C      { def msub   = println("CSub") }

var f: C => C = (c: C)      => new C       // #1
    f         = (c: CSuper) => new CSub    // #2
    f         = (c: CSuper) => new C       // #3
    f         = (c: C)      => new CSub    // #4
    f         = (c: CSub)   => new CSuper  // #5: ERROR!

This script doesn’t produce any output. If you run it, it will fail to compile on the last line.

We start by defining a very simple hierarchy of three classes, C and its superclass CSuper and its subtype CSub. Each one defines a method, which we’ll exploit shortly.

Next we define a var named f on the line with the #1 comment. It is a function with the signature C => C. More precisely, it is of type Function1(-C,+C). To be clear, the value assigned to f is after the equals sign, (c: C) => new C. We actually ignore the input c value and just create a new C.

Now we assign different anonymous function values to f. We use whitespace to make the similarities and differences stand out when comparing the original declaration of f and the subsequent re-assignments. We keep reassigning to f because we are just testing what will and won’t compile at this point. Specifically, we want to know what function values we can legally assign to f: (C) => C.

The second assignment on line #2 assigns (x:CSuper) => new CSub as the function value. This also works, because the argument to Function1 is contravariant, so we can substitute the supertype, while the return type of Function1 is covariant, so our function value can return an instance of the subtype.

The next two lines also work. On line #3, we use a CSuper for the argument, which works as it did in line #2. We return a C, which also works as expected. Similarly, on line #4, we use C as the argument and CSub as the return type, both of which worked fine in the previous lines.

The last line, #5, does not compile because we are attempting to use a covariant argument in a contravariant position. We’re also attempting to use a contravariant return value where only covariant values are allowed.

2 comments

  1. Matt Hellige Posted 1 month, 10 days and 12 hours ago

    I find the last few paragraphs somewhat confusing. The talk about "substituting the supertype" and so on sort of seems to imply substituting a value of that type, which is not what you mean. Also, the setup with the applyFunc function adds extra complication. I think it might be clearer if you just show a series of assignments: val f: C => C = (x:C) => c val f2: C => C = (x:CSuper) => cSub val f3: C => C = (x:CSub) => c // illegal This focuses on the essentials, which to me at least, makes it clearer.

    The following paragraphs are much clearer and give a good intuition.

  2. Dean Wampler Posted 1 month, 10 days and 11 hours ago

    Good suggestion. That is a clearer example. Will change.

Add a comment

Why is the behavior correct in these cases? Here’s where Design by Contract thinking comes in handy. Let’s see how a client might use use some of these definitions of f.

// code-examples/TypeSystem/variances/func2-script.scala
// WON'T COMPILE

class CSuper                { def msuper = println("CSuper") }
class C      extends CSuper { def m      = println("C") }
class CSub   extends C      { def msub   = println("CSub") }

def useF(f: C => C) = {
  val c1 = new C     // #1
  val c2: C = f(c1)  // #2
  c2.msuper          // #3
  c2.m               // #4
}

useF((c: C)      => new C)        // #5
useF((c: CSuper) => new CSub)     // #6
useF((c: CSub)   => {println(c.msub); new CSuper})   // #7: ERROR!

The useF method takes a function C => C as an argument. (We’re just passing function literals now, rather than assigning them to f.) It creates a C (line #1) and passes it to the input function to create a new C (line #2). Then it uses the features of C, namely it calls the msuper and m methods (lines #3 and #4, respectively).

You could say that the useF method specifies a contract of behavior. It expects to be passed a function that can take a C and return a C. It will call the passed-in function, passing a C instance to it, and it will expect to receive a C back.

In line #5, we pass useF a function that takes a C and returns a C. The returned C will work with lines #3 and #4, by definition. All is good.

Finally, we come to the point of this example. In line #6, we pass in a function that is “willing” to accept a CSuper and “promises” to return a CSub. That is, this function is type inferred to be Function1[CSuper,CSub]. In effect, it widens the allowed instances by accepting a supertype. Keep in mind that it will never actually be passed a CSuper by useF, only a C. However, since it can accept a wider set of instances, it will work fine if it only gets C instances.

2 comments

  1. mbaxter Posted 1 month, 1 day and 6 hours ago

    I think you mean to say, 'In line #6' instead of 'In line #5'.

  2. Dean Wampler Posted 29 days and 22 hours ago

    will fix. Thanks!

Add a comment

Similarly, by “promising” to return a CSub, this anonymous function narrows the possible values returned to useF. That’s okay, too, because useF will accept any C in return, so if it only gets CSubs, it will be happy. Lines #3 and #4 will still work.

Applying the same arguments, we can see why the last line in the script, line #7, fails to compile. Now the anonymous function can only accept a CSub, but useF will pass it a C. The body of the anonymous function would now break, because it calls c.msub which doesn’t exist in C. Similarly, returning a CSuper when a C is expected breaks line #4 in useF, because CSuper doesn’t have the m method.

The same arguments are used to explain how contracts can change under inheritance in Design by Contract.

Note that variance annotations only make sense on the type parameters for parameterized types, not parameterized methods, because the annotations affect the behavior of subtyping. Methods aren’t subtyped, but the types that contain them might be subtyped.

Note

The ‘+’ variance annotation means the parameterized type is covariant in the type parameter. The ‘-’ variance annotation means the parameterized type is contravariant in the type parameter. No variance annotation means the parameterized type is invariant in the type parameter.

Finally, the compiler checks your use of variance annotations for problems like the one we just described in the last lines of the examples. Suppose you attempted to define your own function type this way.

trait MyFunction2[+T1, +T2, -R] {
  def apply(v1:T1, v2:T2): R = { ... }
  ...
}

The compiler would throw the following errors for the apply method.

... error: contravariant type R occurs in covariant position in type (T1,T2)R
       def apply(v1:T1, v2:T2):R
           ^
... error: covariant type T1 occurs in contravariant position in type T1 ...
       def apply(v1:T1, v2:T2):R
                 ^
... error: covariant type T2 occurs in contravariant position in type T2 ...
       def apply(v1:T1, v2:T2):R
                        ^

Variance of Mutable Types

All the parameterized types we’ve discussed so far have been immutable types. What about the variance behavior of mutable types? The short answer is that only invariance is allowed. Consider this example.

// code-examples/TypeSystem/variances/mutable-type-variance-script.scala
// WON'T COMPILE: Mutable parameterized types can't have variance annotations

class ContainerPlus[+A](var value: A)      // ERROR
class ContainerMinus[-A](var value: A)     // ERROR

println( new ContainerPlus("Hello World!") )
println( new ContainerMinus("Hello World!") )

Running this script throws the following errors.

... 4: error: covariant type A occurs in contravariant position in type A     of parameter of setter value_=
class ContainerPlus[+A](var value: A)      // ERROR
                             ^
... 5: error: contravariant type A occurs in covariant position in type => A     of method value
class ContainerMinus[-A](var value: A)     // ERROR
                              ^
two errors found

We can make sense of these errors by remembering our discussion of FunctionN type variance under inheritance, where the types of the function arguments are contravariant (i.e., -T1) and the return type is covariant (i.e., +R).

The problem with a mutable type is that at least one of its fields has the equivalent of read and write operations, either through direct access or through accessor methods.

In the first error, we are trying to use a covariant type as an argument to a setter (write) method, but we saw from our discussion of function types that argument types to a method must be contravariant. A covariant type is fine for the getter (read) method.

Similarly, for the second error, we are trying to use a contravariant type as the return value of a read method, which must be covariant. For the write method, the contravariant type is fine.

Hence, the compiler won’t let us use a variance annotation on a type that is used for a mutable field. For this reason, all the mutable parameterized types in the Scala library are invariant in their type parameters. Some of them have corresponding immutable types that have covariant or contravariant parameters.

Variance In Scala vs. Java

As we said, the variance behavior is defined at the declaration site in Scala. In Java, it is defined at the call site. The client of a type defines the variance behavior desired [Naftalin2006]. In other words, when you use a Java generic and specify the type parameter, you also specify the variance behavior (including invariance, which is the default). You can’t specify variance behavior at the definition site in Java, although you can use expressions that look similar. Those expressions define type bounds, which we’ll discuss below.

In Java variance specifications, a wild card ‘?’ always appears before the super or extends keyword, as shown in the previous table. When we said after the table that the “Java Equivalent” column is a bit misleading, we were referring to the differences between declaration vs. call site specifications. There is another way in which the Scala and Java behaviors differ, which we’ll cover in the section called “Existential Types” below.

A drawback of call-site variance specifications is that they force the users of Java generics to understand the type system more thoroughly than is necessary for Scala users, who don’t need to specify this behavior when using parameterized types. (Scala users also benefit greatly from type inference.)

Let’s look at a Java example, a simplified Java version of Scala’s Option, Some, and None types.

// code-examples/TypeSystem/variances/Option.java

package variances;

abstract public class Option<T> {
  abstract public boolean isEmpty();

  abstract public T get();

  public T getOrElse(T t) {
    return isEmpty() ? t : get();
  }
}
// code-examples/TypeSystem/variances/Some.java

package variances;

public class Some<T> extends Option<T> {

  public Some(T value) {
    this.value = value;
  }

  public boolean isEmpty() { return false; }

  private T value;

  public T get() { return value; }

  public String toString() {
    return "Option(" + value + ")";
  }
}
// code-examples/TypeSystem/variances/None.java

package variances;

public class None<T> extends Option<T> {

  public boolean isEmpty() { return true; }

  public T get() { throw new java.util.NoSuchElementException(); }

  public String toString() {
    return "None";
  }
}

Here is an example that uses this Java Option hierarchy.

// code-examples/TypeSystem/variances/OptionExample.java

package variances;
import java.io.*;
import shapes.*;  // From "Introducing Scala" chapter

public class OptionExample {
  static String[] shapeNames = {"Rectangle", "Circle", "Triangle", "Unknown"};
  static public void main(String[] args) {

    Option<? extends Shape> shapeOption =
      makeShape(shapeNames[0], new Point(0.,0.), 2., 5.);
    print(shapeNames[0], shapeOption);

    shapeOption = makeShape(shapeNames[1], new Point(0.,0.), 2.);
    print(shapeNames[1], shapeOption);

    shapeOption = makeShape(shapeNames[2],
      new Point(0.,0.), new Point(2.,0.), new Point(0.,2.));
    print(shapeNames[2], shapeOption);

    shapeOption = makeShape(shapeNames[3]);
    print(shapeNames[3], shapeOption);
  }

  static public Option<? extends Shape> makeShape(String shapeName,
      Object... args) {
    if (shapeName == shapeNames[0])
      return new Some<Rectangle>(new Rectangle((Point) args[0],
        (Double) args[1], (Double) args[2]));
    else if (shapeName == shapeNames[1])
      return new Some<Circle>(new Circle((Point) args[0], (Double) args[1]));
    else if (shapeName == shapeNames[2])
      return new Some<Triangle>(new Triangle((Point) args[0],
        (Point) args[1], (Point) args[2]));
    else
      return new None<Shape>();
  }

  static void print(String name, Option<? extends Shape> shapeOption) {
    System.out.println(name + "? " + shapeOption);
  }
}

OptionExample.main uses the Shape hierarchy from Chapter 1, Zero to Sixty: Introducing Scala, but we have updated it slightly to exploit features that we’ve learned since then, such as case classes.

// code-examples/TypeSystem/shapes/shapes.scala

package shapes {
  case class Point(x: Double, y: Double) {
    override def toString() = "Point(" + x + "," + y + ")"
  }

  abstract class Shape() {
    def draw(): Unit
  }

  case class Circle(center: Point, radius: Double) extends Shape {
    def draw() = println("Circle.draw: " + this)
  }

  case class Rectangle(lowerLeft: Point, height: Double, width: Double)
        extends Shape {
    def draw() = println("Rectangle.draw: " + this)
  }

  case class Triangle(point1: Point, point2: Point, point3: Point)
        extends Shape() {
    def draw() = println("Triangle.draw: " + this)
  }
}

Running OptionExample with scala -cp ... variances.OptionExample produces the following output.

Rectangle? Option(Rectangle(Point(0.0,0.0),2.0,5.0))
Circle? Option(Circle(Point(0.0,0.0),2.0))
Triangle? Option(Triangle(Point(0.0,0.0),Point(2.0,0.0),Point(0.0,2.0)))
Unknown? None

By the way, we are also demonstrating Scala-Java interoperability, which we’ll revisit in the section called “Java Interoperability” in Chapter 14, Scala Tools, Libraries and IDE Support.

OptionExample.main calls the static factory method makeShape, whose arguments are the name of a geometric shape and a variable length list of parameters to pass to the Shape constructors.

Note that makeShape returns Option<? extends Shape> and when we instantiate a Shape, we return a Some parameterized with the Shape subtype it wraps. If an unknown shape name is passed in, then we return a None<Shape>. We must parameterize a None instance with Shape. Because Scala defines a subtype of all types, Nothing, Scala can define None as case object None extends Option[Nothing].

The Java type system provides no way to implement our Java None in a similar way. Having a singleton object None has a number of advantages, including greater efficiency, because we aren’t creating lots of little objects, and unambiguous behavior of equals, because we don’t need to define the semantics of equality between different type instantiations of our Java None<?> type, for example, None<String> vs. None<Shape>.

Finally, note that OptionExample, a client of Option, has to specify type variance, Option<? extends Shape> in several places. In Scala, the client doesn’t carry this burden.

Implementation Notes

The implementation of parameterized types and methods is worth noting. The implementations are generated when the defining source file is compiled. For each type parameter, the implementation assumes that Any subtype could be specified (Object is used in Java generics). These aspects have performance implications that we will revisit when we discuss the @specialized annotation in the section called “Annotations” in Chapter 13, Application Design.

Type Bounds

When defining a parameterized type or method, it may be necessary to specify bounds on the type. For example, a parameterized type might assume that a particular type parameter contains certain methods.

Upper Type Bounds

Consider the overloaded apply methods in object scala.Array that create new arrays. There are optimized implementations for each of the AnyVal types. There is another implementation of apply that is parameterized for any type that is a subtype of AnyRef. Here is the implementation in Scala version 2.7.5.

object Array {
  ...
  def apply[A <: AnyRef](xs: A*): Array[A] = {
    val array = new Array[A](xs.length)
    var i = 0
    for (x <- xs.elements) { array(i) = x; i += 1 }
    array
  }
  ...
}

The type parameter A <: AnyRef means “any type A that is a subtype of AnyRef”. Note that a type is always a subtype and a supertype of itself, so A could also equal AnyRef. So the <: operator indicates that the type to the left must be derived from the type to the right, or that they must be the same type. As we said in the section called “Reserved Words” in Chapter 2, Type Less, Do More, this operator is actually a reserved word in the language.

These bounds are called upper type bounds, following the de facto convention that diagrams of type hierarchies put subtypes below their supertypes. We followed this convention in the diagram shown in the section called “The Scala Type Hierarchy” in Chapter 7, The Scala Object System.

2 comments

  1. Matt Hellige Posted 1 month, 10 days and 12 hours ago

    Not to mention the fact that "sub-" and "super-" imply a vertical ordering... ;)

  2. Dean Wampler Posted 1 month, 10 days and 8 hours ago

    That's pretty much what I meant...

Add a comment

Without the bound in this case, i.e., if the signature were def apply[A](xs: A*): Array[A], the declaration would be ambiguous with the other apply methods for each of the AnyVal types.

Note

The type signature A <: B says that A must be a subtype of B. In Java, this would be expressed as A extends B in a type declaration. This is different than instantiating a type at a call site, where the syntax ? extends B is used in Java, indicating the variance behavior.

Keep in mind the distinction between type variance and type bounds. For a type like List, the variance behavior describes how actual types instantiated from it, like List[AnyRef] and List[String], are related. In this case, List[String] is a subtype of List[AnyRef], since String is a subtype of AnyRef.

In contrast, lower and upper type bounds limit the allowed types that can be used for a type parameter when instantiating a type from a parameterized type. For example, def apply[A <: AnyRef]… says that any type used for A must be a subtype of AnyRef.

Lower Type Bounds

Similarly, there are circumstances when we might want to express that only supertypes of a particular type are allowed. (Recall that a type is also a supertype of itself.) We call these lower type bounds, again because the allowed type would be above the boundary in a typical type hierarchy diagram.

A particularly interesting example is the :: (“cons”) method in class List[+A]. Recall that this operator is used to create a new list by prepending an element to a list.

class List[+A] {
  ...
  def ::[B >: A](x : B) : List[B] = new scala.::(x, this)
  ...
}

The new list will be of type List[B], specifically a scala.::. The :: class (as opposed to the :: method) is derived from List. We’ll come back to it in a moment.

The :: method can prepend an object of a different type from A, the type of the elements in the original list. The compiler will infer the closest common supertype for A and the parameter x. It will use that supertype as B. Here’s an example that prepends a different type of object on a list.

3 comments

  1. Matt Hellige Posted 1 month, 10 days and 12 hours ago

    Don't say "parser": the parser is not the type-checker, and I think it's needlessly confusing. Just say "the compiler will infer..."

    Also, this should be the "least common supertype," not the greatest. The greatest common supertype is always Any.

  2. Dean Wampler Posted 1 month, 10 days and 8 hours ago

    I'm planning to change "parser" to "compiler" globally.

    You're right that I picked the word "greatest" to have the opposite sense of the up/down sense of sub/super. Will fix.

  3. Dean Wampler Posted 1 month, 10 days and 8 hours ago

    "Closest" is the work I'm going with...

Add a comment

// code-examples/TypeSystem/bounds/list-ab-script.scala

val languages = List("Scala", "Java", "Ruby", "C#", "C++", "Python")
val list = 3.14 :: languages
println(list)

The script prints the following output.

List(3.14, Scala, Java, Ruby, C#, C++, Python)

The new list of type List[Any], since Any is the closest common supertype of String and Double. We started with a list of Strings, so A was String. Then we prepended a Double, so the compiler inferred B to be Any, the closest (and only) common supertype.

2 comments

  1. Matt Hellige Posted 1 month, 10 days and 12 hours ago

    Here, too, least rather than greatest.

  2. Dean Wampler Posted 1 month, 10 days and 8 hours ago

    will fix.

Add a comment

Note

The type signature B :> A says that B must be a supertype of A. There is no analog in Java; B super A is not supported.

A Closer Look at Lists

Putting these features together, it’s worth looking at the implementation of the List class in the Scala library. It illustrates several useful idioms for functional-style, immutable data structures that are fully type safe, yet flexible. We won’t show the entire implementation, and we’ll omit the object List, many methods in the List class, and the comments that are used to generate the Scaladocs. We encourage you to look at the complete implementation of List, either by downloading the source distribution from the Scala web site [Scala] or by browsing to the implementation through the Scaladocs page for List. To avoid confusion with scala.List, we’ll use our own package and name, AbbrevList.

// code-examples/TypeSystem/bounds/abbrev-list.scala
// Adapted from scala/List.scala in the Scala version 2.7.5 distribution.

package bounds.abbrevlist

sealed abstract class AbbrevList[+A] {

  def isEmpty: Boolean
  def head: A
  def tail: AbbrevList[A]

  def ::[B >: A] (x: B): AbbrevList[B] = new bounds.abbrevlist.::(x, this)

  final def foreach(f: A => Unit) = {
    var these = this
    while (!these.isEmpty) {
      f(these.head)
      these = these.tail
    }
  }
}

// The empty AbbrevList.

case object AbbrevNil extends AbbrevList[Nothing] {
  override def isEmpty = true

  def head: Nothing =
    throw new NoSuchElementException("head of empty AbbrevList")

  def tail: AbbrevList[Nothing] =
    throw new NoSuchElementException("tail of empty AbbrevList")
}

// A non-empty AbbrevList characterized by a head and a tail.

final case class ::[B](private var hd: B,
    private[abbrevlist] var tl: AbbrevList[B]) extends AbbrevList[B] {

  override def isEmpty: Boolean = false
  def head : B = hd
  def tail : AbbrevList[B] = tl
}

Notice that while AbbrevList is immutable, the internal implementation uses mutable variables, e.g., in forEach.

There are three types defined, forming a sealed hierarchy. AbbrevList (the analog of List) is an abstract trait that declares three abstract methods, isEmpty, head, and tail. It defines the “cons” operator, :: and a foreach method. All the other methods found in List could be implemented with these methods, although some methods (like List.length) use different implementation options for efficiency.

AbbrevNil is the analog of Nil. It is a case object that extends AbbrevList[Nothing]. It returns true from isEmpty and it throws an exception from head and tail. Because AbbrevNil (and Nil) have essentially no state and behavior, having an object rather than a class eliminates unnecessary copies, makes equals fast and simple, etc.

The :: class is the analog of scala.:: derived from List. It is declared final. Its arguments are the element to become the head of the new list and an existing list, which will be the tail of the new list. Note that these values are stored directly as fields. The head and tail methods defined in AbbrevList are just reader methods for these fields. There is no other data structure required to represent the list.

This is why prepending a new element to create a new list is an O(1) operation. The List class also has a deprecated method + for creating a new list by appending an element to the end of an existing list. That operation is O(N), where N is the length of the list.

As you build up new lists by prepending elements to other lists, a nested hierarchy of :: instances is created. Because the lists are immutable, there are no concerns about corruption if one of the :: is changed in some way.

You can see this nesting if you print out a list, exploiting the toString method generated because of the case keyword. Here is an example scala session.

$ scala -cp ...
Welcome to Scala version 2.7.5.final ...
Type in expressions to have them evaluated.
Type :help for more information.

scala> import bounds.abbrevlist._
import bounds.abbrevlist._

scala> 1 :: 2 :: 3 :: AbbrevNil
res1: bounds.abbrevlist.AbbrevList[Int] = ::(1,::(2,::(3,AbbrevNil)))

Note the output on the last line, which shows the nesting of (head,tail) elements.

For another example using similar approaches, this time for defining a Stack, see http://www.scala-lang.org/node/129.

Views and View Bounds

We’ve seen many examples where an implicit method was used to convert one type to another, for example to give the appearance of adding new methods to an existing type, the so-called “pimp my library” pattern. We used this pattern extensively in Chapter 11, Domain-Specific Languages in Scala. You can also use function values that have the implicit keyword. We’ll see an examples of both shortly.

A view is an implicit value of function type that converts a type A to B. The function has the type A => B or (=> A) => B (recall that (=> A) is a by-name parameter). An in-scope implicit method with the same signature can also be used as a view, e.g., an implicit method imported from an object. The term view conveys the sense of having a view from one type (A) to another type (B).

2 comments

  1. Matt Hellige Posted 1 month, 10 days and 11 hours ago

    Both function values and methods must be marked "implicit" in order to be considered as views, right? Or maybe this has changed? If so, I'd say "A view is a value of function type marked 'implicit' that..." and "An in-scope method with the same signature and the 'implicit' qualifier is also a view."

  2. Dean Wampler Posted 1 month, 10 days and 7 hours ago

    Thanks. Forgot to mention the implicit keyword (for both in-scope methods and function values), etc.

Add a comment

A view is applied in two circumstances.

  1. When a type A is used in a context where another type B is expected and there is a view in scope that can convert A to B.
  2. When a non-existent member m of a type A is referenced, but there is an in-scope view that can convert A to a B that has the m member.

A common example of the second circumstance is the x -> y initialization syntax for Maps, which triggers invocation of Predef.anyToArrowAssoc(x), as we discussed in the section called “The Predef Object” in Chapter 7, The Scala Object System.

For an example of the first circumstance, Predef also defines many views for converting between AnyVal types and for converting an AnyVal type to its corresponding java.lang type. For example, double2Double converts a scala.Double to a java.lang.Double.

A view bound in a type declaration is indicated with the <% keyword, e.g., A <% B. It allows any type to be used for A if it can be converted to B using a view.

A method or class containing such a type parameter is treated as being equivalent to a corresponding method or class with an extra argument list with one element, a view. For example, consider the following method defintion with a view bound.

def m [A <% B](arglist): R = ...

It is effectively the same as this method definition.

def m [A](arglist)(implicit viewAB: A => B): R = ...

(The implicit parameter viewAB would be given a unique name by the compiler.) Note that we have an additional argument list, as opposed to an additional argument in the existing argument list.

Why does this transformation work? We said that a valid A must have a view in scope that transforms it to a B. The implicit viewAB argument will get invoked inside m to convert all A instances to B instances where needed.

For this to work, there must be a view of the correct type in scope to satisfy the implicit argument. You could also pass a function with the correct signature explicitly as the second argument list when you call m. However, there is one situation where this won’t work, which we’ll describe after our example below.

For view bounds on types, the implicit view argument list would be added to the primary constructor.

Note

Traits can’t have view bounds for their type parameters, because they can’t have constructor argument lists.

To make this more concrete, let’s use view bounds to implement a LinkedList class that uses Nodes, where each Node has a payload and a reference to the next Node in the list. First, here is a hierarchy of Nodes.

// code-examples/TypeSystem/bounds/node.scala

package bounds

abstract trait Node[+A] {
  def payload: A
  def next: Node[A]
}

case class ::[+A](val payload: A, val next: Node[A]) extends Node[A] {
  override def toString =
    String.format("(%s :: %s)", payload.toString, next.toString)
}

object NilNode extends Node[Nothing] {
  def payload = throw new NoSuchElementException("No payload in NilNode")
  def next    = throw new NoSuchElementException("No next in NilNode")

  override def toString = "*"
}

This type hierarchy is modeled after List and AbbrevList above. The :: type represents intermediate nodes and NilNode is analogous to Nil for Lists. We also override toString to give us convenient output, which we’ll examine shortly.

The following script defines a LinkedList type that uses Nodes.

// code-examples/TypeSystem/bounds/view-bounds-script.scala

import bounds._

implicit def any2Node[A](x: A): Node[A] = bounds.::[A](x, NilNode)

case class LinkedList[A <% Node[A]](val head: Node[A]) {

  def ::[B >: A <% Node[B]](x: Node[B]) =
    LinkedList(bounds.::(x.payload, head))

  override def toString = head.toString
}

val list1 = LinkedList(1)
val list2 = 2 :: list1
val list3 = 3 :: list2
val list4 = "FOUR!" :: list3

println(list1)
println(list2)
println(list3)
println(list4)

It starts with a definition of a parameterized implicit method, any2Node, that converts A to Node[A]. It will be used as the implicit view argument when we work with LinkedLists. It creates a “leaf” node using a bounds.:: node with a reference to NilNode as the “next” element in the list.

An alternative would be a function value that converts Any to Node[Any].

implicit val any2Node = (a: Any) => bounds.::[Any](a, NilNode)

Otherwise, the script would run the same, except that some of the temporary lists would be using Node[Any] rather than Node[Int].

Look at the declaration of LinkedList.

case class LinkedList[A <% Node[A]](val head: Node[A]) { ... }

It defines a view bound on A and takes a single argument, the head Node of the list (which may be the head of a chain of Nodes). As we see later in the script, even though the constructor expects a Node[A] argument, we can pass it an A and the implicit view any2Node will get invoked. The beauty of this approach is that a client never has to worry about proper construction of Nodes. The machinery handles that process automatically.

The class also has a “cons” operator.

def ::[B >: A <% Node[B]](x: Node[B]) = ...

The type parameter means ``B is lower bounded by (i.e., is a supertype of) A and B also has a view bound of B <% Node[B]. As we saw for List and AbbrevList, the lower bound allows us to prepend items of different types from the original A type. This method will have its own implicit view argument, but our parameterized, implicit method, any2Node, will be used for this argument, too.

We mentioned previously that if you don’t have a view in scope, you could pass a “non-implicit” converter as the second argument list explicitly. This actually won’t work in our example, because the constructor and :: method in LinkedList take Node[A] arguments, but we call them with Ints and Strings. We would have to call them with Node[Int] and Node[String] arguments explicitly. We would also have to invoke :: in an ugly way, val list2 = list1.::(2)(converter), for example.

Let’s clarify the syntax a bit. When you see B >: A <% Node[B], it’s tempting to assume that the <% should apply to A in this expression. It actually applies to B. The grammar for type parameters, including view bounds, is the following [ScalaSpec2009].

TypeParam ::= (id | ‘_’) [TypeParamClause] [‘>:’ Type] [‘<:’ Type] [‘<%’ Type]
TypeParamClause ::= ‘[’ VariantTypeParam {‘,’ VariantTypeParam} ‘]’
VariantTypeParam ::= [‘+’ | ‘’] TypeParam

So, yes, you can have some very complex, hierarchical types! In our :: method, the id is B, the TypeParamClause is empty, and we have the >: A and <% Node[B] expressions on the right. Again, all the bounds expressions apply to the first id (B) or the underscore ‘_’.

The underscore ‘_’ is used for existential types, which we’ll cover below, in the section called “Existential Types”.

2 comments

  1. Matt Hellige Posted 1 month, 10 days and 11 hours ago

    I'm not sure if this is right. I think the _ is only used in the case of existential types (where it expands to a forSome clause). Are you sure it's also used in pattern matching? You may well be right, but it might be worth checking.

  2. Dean Wampler Posted 1 month, 10 days and 6 hours ago

    I'm pretty sure you're right; the underscore only applies to existential types. will fix.

Add a comment

Finally, we create a LinkedList in the script, prepend some values to create new lists, and then print them out.

1 :: *
2 :: 1 :: *
3 :: 2 :: 1 :: *
FOUR! :: 3 :: 2 :: 1 :: *

To recap, the view bounds let us work with “payloads” of Ints and Strings while the implementation handled the necessary conversions to Nodes.

View bounds are not used as often as upper and lower bounds, but they provide an elegant mechanism for those times when automatic coercion from one type into another is useful. As always, use implicits with caution; implicit conversions are far from obvious when reading code and debugging mysterious behavior.

Nothing and Null

In the section called “The Scala Type Hierarchy” in Chapter 7, The Scala Object System, we mentioned that Null is a subtype of all AnyRef types and Nothing is a subtype of all types, including Null.

Null is declared as a final trait (so it can’t be subtyped) and it has only one instance, null. Since Null is a subtype of all AnyRef types, you can always assign null as an instance of any of those types. Java, in contrast, simply treats null as a keyword with special handling by the compiler. However, Java’s null actually behaves as if it were a subtype of all reference types, just like Scala’s Null.

On the other hand, since Null is not a subtype of AnyVal, it is not possible to assign null to an Int, for example, which is also consistent with the primitive semantics in Java.

Nothing is also a final trait, but it has no instances. However, it is still useful for defining types. The best example is Nil, the empty list, which is a case object. It is of type List[Nothing]. Because lists are covariant in Scala, as we saw above, this makes Nil an instance of List[T], for any type T. We also exploited this feature above in our AbbrevList and LinkedList implementations.

Understanding Abstract Types

Besides parameterized types, which are common in statically-typed, object-oriented languages, Scala also supports abstract types, which are common in functional languages. We introduced abstract types in the section called “Abstract Types And Parameterized Types” in Chapter 2, Type Less, Do More.

These two features overlap somewhat. Technically, you could implement almost all the idioms that parameterized types support using abstract types and vice versa. However, in practice, each feature is a natural fit for different design problems.

Recall our version of Observer that uses abstract types in Chapter 6, Advanced Object-Oriented Programming In Scala.

// code-examples/AdvOOP/observer/observer2.scala

package observer

trait AbstractSubject {
  type Observer

  private var observers = List[Observer]()
  def addObserver(observer:Observer) = observers ::= observer
  def notifyObservers = observers foreach (notify(_))

  def notify(observer: Observer): Unit
}

trait SubjectForReceiveUpdateObservers extends AbstractSubject {
  type Observer = { def receiveUpdate(subject: Any) }

  def notify(observer: Observer): Unit = observer.receiveUpdate(this)
}

trait SubjectForFunctionalObservers extends AbstractSubject {
  type Observer = (AbstractSubject) => Unit

  def notify(observer: Observer): Unit = observer(this)
}

AbstractSubject declares a type Observer with no type bounds. It is defined in the two derived traits. In SubjectForReceiveUpdateObservers, it is defined to be a structural type. In SubjectForFunctionalObservers, it is defined to be a function type. We’ll have more to say about structural and function types later in this chapter.

We can also use type bounds when we declare or refine the declaration of abstract types. We saw a simple example previously in this chapter in the section called “Type Projections” where we had a declaration type t <: AnyRef. That is, t had an upper type bound (superclass) of AnyRef. AnyVal types weren’t allowed.

We can also have lower type bounds (subclasses) and we can use most of the value types (see the section called “Value Types” below) in the bounds expressions. Here is an example illustrating the most common options.

// code-examples/TypeSystem/abstracttypes/abs-type-examples-script.scala

trait exampleTrait {
  type t1               // Unconstrained
  type t2 >: t3 <: t1   // t2 must be a supertype of t3 and a subtype of t1
  type t3 <: t1         // t3 must be a subtype of t1
  type t4               // Unconstrained
  type t5 = List[t4]    // List of t4, whatever t4 will eventually be...

  val v1: t1            // Can't initialize until t1 defined.
  val v3: t3            // etc.
  val v2: t2            // ...
  val v4: t4            // ...
  val v5: t5            // ...
}

trait T1 { val name1: String }
trait T2 extends T1 { val name2: String }
class C(val name1: String, val name2: String) extends T2

object example extends exampleTrait {
  type t1 = T1
  type t2 = T2
  type t3 = C
  type t4 = Int

  val v1 = new T1 { val name1 = "T1"}
  val v3 = new C("C1", "C2")
  val v2 = new T2 { val name1 = "T1"; val name2 = "T2" }
  val v4 = 10
  val v5 = List(1,2,3,4,5)
}

The comments explain most of the details. The relationships between t1, t2, and t3 have some interesting points. First, the declaration of t2 says that it must be “between” t1 and t3. Whatever t1 becomes, it must be a super class of t2 (or equal to it) and t3 must be a subclass of t2 (or equal to it).

Remember from the section called “Type Bounds” that we are making a declaration of the first type after the type keyword, t2, not the type in the middle, t3. The rest of the expression is telling us the bounds of t2.

Consider the next line that declares t3 to be a subtype of t1. If you were to omit the type bound, the compiler would throw an error, because t3 <: t1 is implied by the previous declaration of t2. That doesn’t mean that you can leave out the declaration of t3. It has to be there, but it also has to show a consistent type bound with the one implied in the t2 declaration.

When we revisit the Observer pattern in the section called “Self-Type Annotations and Abstract Type Members” in Chapter 13, Application Design, we’ll see another example of type bounds used on abstract types. We’ll see a problem they can cause, along with an elegant solution.

Finally, abstract types don’t have variance annotations.

// code-examples/TypeSystem/abstracttypes/abs-type-variances-wont-compile.scala
// WON'T COMPILE

trait T1 { val name1: String }
trait T2 extends T1 { val name2: String }
class C(val name1: String, val name2: String) extends T2

trait T {
  type t: +T1   // ERROR, no +/- type variance annotations
  val v
}

Remember that the abstract types are members of the enclosing type, not type parameters, as for parameterized types. The enclosing type may have an inheritance relationship with other types, but member types behave just like member methods and variables. They don’t affect the inheritance relationships of their enclosing type. Like other members, abstract types can be declared abstract or concrete. However, they can also be refined in subtypes without being fully defined, unlike variables and methods. Of course, instances can only be created when the abstract types are given concrete definitions.

Parameterized Types vs. Abstract Types

When should you use parameterized types vs. abstract types? Parameterized types are the most natural fit for parameterized container types like List and Option. Consider the declaration of Some from the standard library.

case final class Some[+A](val x : A) { ... }

If we tried to convert this to use abstract types, we might start with the following.

case final class Some(val x : ???) {
  type A
  ...
}

What should be the type of the field x? We can’t use A because it’s not in scope at the point of the constructor argument. We could use Any, but that defeats the value of having appropriately-typed declarations.

If a type will have constructor arguments declared using a “placeholder” type that has not yet been defined, then parameterized types are the only good solution (short of using Any or AnyRef).

You can use abstract types as method arguments and return values within a function. However, two problems can arise. First, you can run into problems with path-dependent types (discussed below in the section called “Path-Dependent Types”), where the compiler thinks you are trying to use an incompatible type in a particular context when in fact they are paths to compatible types. Second, it’s awkward to express methods like List.:: (“cons”) using abstract types where type changes (expansion in this case) can occur.

class List[+A] {
  ...
  def ::[B >: A](x : B) : List[B] = new scala.::(x, this)
  ...
}

Also, if you want to express variance under inheritance that is tied to the type abstractions, then parameterized types with variance annotations make these behaviors obvious and explicit.

These limitations of abstract types really reflect the tension between object-oriented inheritance and the origin of abstract types in pure functional programming type systems, which don’t have inheritance. Parameterized types are more popular in object-oriented languages because they handle inheritance more naturally in most circumstances.

On the other hand, sometimes it’s useful to refer to a type abstraction as a member of another type, as opposed to a parameter used to construct new types from a parameterized type. Refining an abstract type declaration through a series of enclosing type refinements can be quite elegant.

trait T1 {
  type t
  val v: t
}
trait T2 extends T1 {
  type t <: SomeType1
}
trait T3 extends T2 {
  type t <: SomeType2  // where SomeType2 <: SomeType1
}
class C extends T3 {
  type t = Concrete    // where Concrete <: SomeType2
  val v = new Concrete(...)
}
...

This example also shows that abstract types are often used to declare abstract variables of the same type. Less frequently, they are used for method declarations.

When the abstract variables are eventually made concrete, they can either be defined inside the type body, much as they were originally declared, or they can be initialized through constructor arguments. Using constructor arguments lets the user decide on the actual values, while initializing them in the body lets the type designer decide on the appropriate value.

We used constructor arguments in the brief BulkReader example we presented in the section called “Abstract Types And Parameterized Types” in Chapter 2, Type Less, Do More.

// code-examples/TypeLessDoMore/abstract-types-script.scala

import java.io._

abstract class BulkReader {
  type In
  val source: In
  def read: String
}

class StringBulkReader(val source: String) extends BulkReader {
  type In = String
  def read = source
}

class FileBulkReader(val source: File) extends BulkReader {
  type In = File
  def read = {
    val in = new BufferedInputStream(new FileInputStream(source))
    val numBytes = in.available()
    val bytes = new Array[Byte](numBytes)
    in.read(bytes, 0, numBytes)
    new String(bytes)
  }
}

println( new StringBulkReader("Hello Scala!").read )
println( new FileBulkReader(new File("abstract-types-script.scala")).read )

If you come from an object-oriented background, you will naturally tend to use parameterized types more often than abstract types. The Scala standard library tends to emphasize parameterized types, too. Still, you should learn the merits of abstract types and use them when they make sense.

Path-Dependent Types

Languages that let you nest types provide ways to refer to those type paths. Scala provides a rich syntax for path-dependent types. Although you will probably use them rarely, it’s useful to understand the basics, as compiler errors often contain type paths.

Consider the following example.

// code-examples/TypeSystem/typepaths/type-path-wont-compile.scala
// ERROR: Won't compile

trait Service {
  trait Logger {
    def log(message: String): Unit
  }
  val logger: Logger

  def run = {
    logger.log("Starting " + getClass.getSimpleName + ":")
    doRun
  }

  protected def doRun: Boolean
}

object MyService1 extends Service {
  class MyService1Logger extends Logger {
    def log(message: String) = println("1: "+message)
  }
  override val logger = new MyService1Logger
  def doRun = true  // do some real work...
}

object MyService2 extends Service {
  override val logger = MyService1.logger  // ERROR
  def doRun = true  // do some real work...
}

If you compile this file you get the following error.

...:27: error: error overriding value logger in trait Service of type     MyService2.Logger;
 value logger has incompatible type MyService1.MyService1Logger
  override val logger = MyService1.logger  // ERROR
               ^
one error found

The error says that the logger value in MyService2 on line 25 has type MyService2.Logger, even though it’s declared to be of type Logger in the parent Service trait. Also, we’re trying to assign it a value of type MyService1.MyService1Logger.

These three types are different in Scala. Logger is nested in Service, which is the parent of MyService1 and MyService2. In Scala, that means that the the nested Logger type is unique for each of the service types. The actual type is path dependent.

In this case, the easiest solution is to move the declaration of Logger outside of Service, thereby removing the path dependency. In other cases, it’s possible to qualify the type so that it resolves to what you want.

There are several kinds of type paths.

C.this

For a class C, you can use C.this or this inside the body to refer to the current instance.

class C1 {
  var x = "1"
  def setX1(x:String) = this.x = x
  def setX2(x:String) = C1.this.x = x
}

Both setX1 and setX2 have the same effect, because C1.this is equivalent to this.

Inside a type body and outside a method definition, this refers to the type itself.

trait T1 {
  class C
  val c1 = new C
  val c2 = new this.C
}

The values c1 and c2 have the same type. The this in the expression this.C refers to the trait T1.

C.super

You can refer specifically to the parent of a type with super.

class C2 extends C1
class C3 extends C2 {
  def setX3(x:String) = super.setX1(x)
  def setX4(x:String) = C3.super.setX1(x)
  def setX5(x:String) = C3.super[C2].setX1(x)
}

C3.super is equivalent to super in this example. If you want to refer specifically to one of the parents of a type, you can qualify super with the type, as shown in setX5. This is particularly useful for the case where a type mixes in several traits, each of which overrides the same method. If you need access to one of the methods in a specific trait, you can qualify super. However, this qualification can’t refer to “grandparent” types.

What if you are calling super in a class with several mixins and it extends another type? To which type does super bind? Without the qualification, the rules of linearization determine the target of super (see the section called “Linearization of an Object’s Hierarchy” in Chapter 7, The Scala Object System).

Just as for this, you can use super to refer to the parent type in a type body outside a method.

class C4 {
  class C5
}
class C6 extends C4 {
  val c5a = new C5
  val c5b = new super.C5
}

Both c5a and c5b have the same type.

path.x

You can reach a nested type with a period-delimited path expression.

package P1 {
  object O1 {
    object O2 {
      val name = "name"
    }
  }
}
class C7 {
  val name = P1.O1.O2.name
}

C7.name uses a path to the name value in O2. The elements of a type path must be stable, which roughly means that all elements in the path must be packages, singleton objects, or type declarations that alias the same. The last element in the path can be a class or trait. See [ScalaSpec2009] for the details.

object O3 {
  object O4 {
    type t = java.io.File
    class C
    trait T
  }
  class C2 {
    type t = Int
  }
}
class C8 {
  type t1 = O3.O4.t
  type t2 = O3.O4.C
  type t3 = O3.O4.T
//  type t4 = O3.C2.t   // ERROR: C2 is not a "value" in O3
}

Value Types

Because Scala is strongly and statically typed, every value has a type. The term value types refers to all the different forms these types take, so it encompasses many forms that are now familiar to us, plus a few new ones we haven’t encountered until now.

Warning

We are using the term value type here in the same way the term is used by [ScalaSpec2009]. However, elsewhere in the book we also follow the specification’s overloaded use of the term to refer to all subtypes of AnyVal.

Type Designators

The conventional type ids we commonly use are called type designators.

class Person              // "Person" is a type designator.
object O { type t }       // "O" and "t" are type designators.
...

They are actually a short hand syntax for type projections, which we cover below.

Tuples

A value of the form (x1, … xN) is a tuple value type.

Parameterized Types

When we create a type from a parameterized type, e.g., List[Int] and List[String] from List[A], the types List[Int] and List[String] are value types, because they are associated with declared values, e.g., val names = List[String]().

Annotated Types

When we annotate a type, e.g., @serializable @cloneable class C(val x:String), the actual type includes the annotations.

Compound Types

A declaration of the form T1 extends T2 with T3 { R }, where R is the refinement (body), declares a compound type. Any declarations in the refinement are part of the compound type definition. The notion of compound types accounts for the fact that not all types are named, since we can have anonymous types, such as this example scala session.

scala> val x = new T1 with T2 {
        type z = String
        val v: z = "Z"
}
x: java.lang.Object with T1 with T2{type z = String; def zv: this.z} =     $anon$1@9d9347d

Note that path-dependent type this.z in the output.

A particularly interesting case is a declaration of the form val x = new { R }, i.e., without any type ids. This is equivalent to val x = new AnyRef { R }.

Infix Types

Some parameterized types take two type arguments, e.g., scala.Either[+A,+B]. Scala allows you to declare instances of these types using an infix notation, e.g., a Either b. Consider the following script that uses +Either.

// code-examples/TypeSystem/valuetypes/infix-types-script.scala

def attempt(operation: => Boolean): Throwable Either Boolean = try {
  Right(operation)
} catch {
  case t: Throwable => Left(t)
}

println(attempt { throw new RuntimeException("Boo!") })
println(attempt { true })
println(attempt { false })

The attempt method will evaluate the call-by-value parameter operation and return its Boolean result, wrapped in a Right or any Throwable that is caught, wrapped in a Left. The script produces this output.

1 comment

  1. Dirk Kuzemczak Posted 21 days and 18 hours ago

    the "call-by-name" parameter

Add a comment

Left(java.lang.RuntimeException: Boo!)
Right(true)
Right(false)

Notice the declared return value, Throwable Either Boolean. It is identical to Either[Throwable, Boolean]. Recall from the section called “The Scala Type Hierarchy” that when using this exception-handling idiom with Either, it is conventional to use Left for the exception and Right for the normal return value.

Function Types

The functions we have been writing are also typed. (T1, T2, … TN) => R is the type for all functions that take N arguments and return a value of type R.

When there is only one argument, you can drop the parentheses, T => R. A Function that takes a call-by-name parameter (as discussed in Chapter 8, Functional Programming in Scala) has the type (=>T) => R. We used a call-by-name argument in our attempt example in the previous section.

Recall that everything in Scala is an object, even functions. The Scala library defines traits for each FunctionN, for N from 0 to 22, inclusive. Here, for example, is the version 2.7.5 source for scala.Function3, omitting most comments and a few other details that don’t concern us now.

// From Scala version 2.7.5: scala.Function3 (excerpt).
package scala

trait Function3[-T1, -T2, -T3, +R] extends AnyRef {
  def apply(v1:T1, v2:T2, v3:T3): R
  override def toString() = "<function>"

  /** f(x1,x2,x3)  == (f.curry)(x1)(x2)(x3)
   */
  def curry: T1 => T2 => T3 => R = {
    (x1: T1) => (x2: T2) => (x3: T3) => apply(x1,x2,x3)
  }
}

As we discussed in the section called “Variance Under Inheritance” above, The FunctionN traits are contravariant in the type parameters for the arguments and covariant in the return type parameter.

Recall that when you reference any object followed by an argument list, Scala calls the apply method on the object. In this way, any object with an apply method can also be considered a function, providing a nice symmetry with the object-oriented nature of Scala.

When you define a function value, the compiler instantiates the appropriate FunctionN object and uses your definition of the function as the body of apply.

// code-examples/TypeSystem/valuetypes/function-types-script.scala

val capitalizer = (s: String) => s.toUpperCase

val capitalizer2 = new Function1[String,String] {
  def apply(s: String) = s.toUpperCase
}

println( List("Programming", "Scala") map capitalizer)
println( List("Programming", "Scala") map capitalizer2)

The capitalizer and capitalizer2 function values are effectively the same, where the latter mimics the compiler’s output.

We discussed the curry method previously in the section called “Currying” in Chapter 8, Functional Programming in Scala. It returns a new function with N argument lists, each of which has a single argument taken from the original argument list of N arguments. Note that the same apply method is invoked.

// code-examples/TypeSystem/valuetypes/curried-function-script.scala

val f  = (x: Double, y: Double, z: Double) => x * y / z
val fc = f.curry

val answer1 = f(2., 5., 4.)
val answer2 = fc(2.)(5.)(4.)
println( answer1 + " == " + answer2 + "? " + (answer1 == answer2))

val fc1 = fc(2.)
val fc2 = fc1(5.)
val answer3 = fc2(4.)
println( answer3 + " == " + answer2 + "? " + (answer3 == answer2))

This script produces the following output.

2.5 == 2.5? true
2.5 == 2.5? true

In the first part of the script, we define a Function3 value f that does Double arithmetic. We create a new function value fc by currying f. Then we call both functions with the same arguments and print out the results. As expected, they both produce the same output. (There are no concerns about rounding errors in the comparison here; recall that both functions call the same apply method, so they must return the same value.)

In the second part of the script, we exploit the feature of curried functions that we can partially apply arguments, creating new functions, until we apply all the arguments. The example also helps us make sense of the declaration of curry in Function3.

Functions are right-associative, so a type T1 => T2 => T3 => R is equivalent to T1 => (T2 => (T3 => R)). We see this in the script. In the statement val fc1 = fc(2.), we call fc with just the first argument list (corresponding to T1 equals Double). It returns a new function of type T2 => (T3 => R) or Double => (Double => Double), in our case.

Next, in val fc2 = fc1(5.), we supply the second (T2) argument, returning a new function of type T3 => R, that is Double => Double. Finally, in val answer3 = fc2(4.) we supply the last argument to compute the value of type R, that is Double.

Note

A type T1 => T2 => T3 => R is equivalent to T1 => (T2 => (T3 => R)). When we call a function of this type with a value for T1, it returns a new function of type T2 => (T3 => R), and so forth.

Finally, since functions are instances of traits, you can use the traits as parents of other types. In the Scala library, Seq[+A] is a subclass of PartialFunction[Int,A], which is a subclass of (Int) => A, i.e., Function1[Int,A].

Type Projections

Type projections are a way to refer to a type declaration nested in another type.

// code-examples/TypeSystem/valuetypes/type-projection-script.scala

trait T {
  type t <: AnyRef
}
class C1 extends T {
  type t = String
}
class C2 extends C1

val ic1: C1#t = "C1"
val ic2: C2#t = "C2"
println(ic1)
println(ic2)

Both C1#t and C2#t are String. You can also reference the abstract type T#t, but you can’t use it in a declaration because it is abstract.

Singleton Types

If you have a value v of a subtype of AnyRef, including null, you can get its singleton type using the expression v.type. These expressions can be used as types in declarations. This feature is useful on rare occasions to work around the fact that types are path dependent, which we discussed in the section called “Path-Dependent Types” above. In these cases an object may have a path dependent type that appears to be incompatible with another path dependent type, when in fact they are compatible. Using the v.type expression retrieves the singleton type, a “unique” type that eliminates the path dependency. Two values v1 and v2 may have different path-dependent types, but they could have the same singleton type.

This example uses the singleton type for one value in a declaration of another.

class C {
  val x = "Cx"
}
val c = new C
val x: c.x.type = c.x

Self Type Annotations

You can use this in a method to refer to the enclosing type, which is useful for referencing a member of the type. Using this is not usually necessary for this purpose, but it’s useful occasionally for disambiguating a reference when several values are in scope with the same name. By default, the type of this is the same as the enclosing type, but this is not really essential.

Self-type annotations let you specify additional type expectations for this and they can be used to create aliases for this. Let’s consider the latter case first.

// code-examples/TypeSystem/selftype/this-alias-script.scala

class C1 { self =>
  def talk(message: String) = println("C1.talk: " + message)
  class C2 {
    class C3 {
      def talk(message: String) = self.talk("C3.talk: " + message)
    }
    val c3 = new C3
  }
  val c2 = new C2
}
val c1 = new C1
c1.talk("Hello")
c1.c2.c3.talk("World")

It prints the following.

C1.talk: Hello
C1.talk: C3.talk: World

We give the outer scope (C1) this the alias self, so we can easily refer to it in C3. We could use self within any method inside the body of C1 or its nested types. Note that the name self is arbitrary, but it is somewhat conventional. In fact, you could say this =>, but it would be completely redundant.

If the self-type annotation has types in the annotation, we get some very different benefits.

// code-examples/TypeSystem/selftype/selftype-script.scala

trait Persistence {
  def startPersistence: Unit
}

trait Midtier {
  def startMidtier: Unit
}

trait UI {
  def startUI: Unit
}

trait Database extends Persistence {
  def startPersistence = println("Starting Database")
}

trait ComputeCluster extends Midtier {
  def startMidtier = println("Starting ComputeCluster")
}

trait WebUI extends UI {
  def startUI = println("Starting WebUI")
}

trait App {
  self: Persistence with Midtier with UI =>

  def run = {
    startPersistence
    startMidtier
    startUI
  }
}

object MyApp extends App with Database with ComputeCluster with WebUI

MyApp.run

This script shows a schematic layout for an App (application) infrastructure supporting several tiers/components, persistent storage, midtier, and UI. We’ll explore this approach to component design in more detail in Chapter 13, Application Design.

For now, we just care about the role of self types. Each abstract trait declares a “start” method that does the work of initializing the tier. (We’re ignoring issues like success vs. failure of startup, etc.) Each abstract tier is implemented by a corresponding concrete trait (not a class, so we can use them as mixins). We have traits for database persistence, some sort of computation cluster to do the heavy lifting for the business logic, and a web-based UI.

The App trait wires the tiers together. For example, it does the work of starting the tiers in the run method.

Note the self-type annotation, self: Persistence with Midtier with UI =>. It has two practical effects.

  1. The body of the trait can assume it is an instance of Persistence, Midtier, and UI, so it can call methods defined in those types, whether or not they are actually defined at this point. We’re doing just that in run.
  2. The concrete type that mixes in this trait must also mix in these three other traits or descendants of them.

In other words, the self type in App specifies dependencies on other components. These dependencies are satisfied in MyApp, which mixes in the concrete traits for the three tiers.

We could have declared App using inheritance instead.

trait App with Persistence with Midtier with UI {

  def run = { ... }
}

This is effectively the same. As we said, the self-type annotation lets the App assume it is of type Persistence, etc.. That’s exactly what happens when you mix in a trait, too.

Why, then, are self types useful if they appear to be equivalent to inheritance? There are some theoretical reasons and a few special cases where self-type annotations offer unique benefits. In practice, you could use inheritance for almost all cases. By convention, people use inheritance when they want to imply that a type behaves as (inherits from) another type and they use self-type annotations when they want to express a dependency between a type and other types [McIver2009].

In our case, we don’t really think of an App as being a UI, database, etc. We think of an App as being composed of those things. Note that in most object-oriented languages, you would express this compositional dependency with member fields, especially if your language doesn’t support mixin composition, like Java. For example, you might write App in Java this way.

// code-examples/TypeSystem/selftype/JavaApp.java

package selftype;

public abstract class JavaApp {
  public interface Persistence {
    public void startPersistence();
  }

  public interface Midtier {
    public void startMidtier();
  }

  public interface UI {
    public void startUI();
  }

  private Persistence persistence;
  private Midtier midtier;
  private UI ui;

  public JavaApp(Persistence persistence, Midtier midtier, UI ui) {
    this.persistence = persistence;
    this.midtier = midtier;
    this.ui = ui;
  }

  public void run() {
    persistence.startPersistence();
    midtier.startMidtier();
    ui.startUI();
  }
}

(We nested the component interfaces inside JavaApp to avoid creating separate files for each one!) You can certainly write applications this way in Scala. However, the self-type approach turns programmatic dependency resolution, i.e., passing dependencies to constructors or setter methods at runtime, into declarative dependency resolution at compile time, which catches errors earlier. Declarative programming, which is a hallmark of functional programming, is generally more robust, succinct, and clear, compared to imperative programming.

We will return to self-type annotations as a component composition model in Chapter 13, Application Design. See the the section called “Self-Type Annotations and Abstract Type Members” and the section called “Dependency Injection in Scala: The Cake Pattern” sections in that chapter.

Structural Types

You can think of structural types as a type-safe approach to duck typing, the popular name for the way method resolution works in dynamically typed languages. In Ruby, for example, when you write starFighter.shootWeapons, the runtime looks for a shootWeapons method on the object referenced by starFighter. That method, if found, might have been defined in the class used to instantiate starFighter or one of its parents or “included” modules. The method might also have been added to the object using the metaprogramming facility of Ruby. Finally, the object might override the catch-all method_missing method and do something reasonable when the object receives the shootWeapons “message”.

Scala doesn’t support this kind of method resolution, Instead, Scala allows you to specify that an object must adhere to a certain structure: that it contains certain types, fields, or methods, without concern for the actual type of the object. We first encountered structural types near the beginning of Chapter 4, Traits. Here is the example we saw then, a variation of the Observer pattern.

// code-examples/Traits/observer/observer.scala

package observer

trait Subject {
  type Observer = { def receiveUpdate(subject: Any) }

  private var observers = List[Observer]()
  def addObserver(observer:Observer) = observers ::= observer
  def notifyObservers = observers foreach (_.receiveUpdate(this))
}

The declaration type Observer = { def receiveUpdate(subject: Any) } says that any valid observer must have the receiveUpdate method. It doesn’t matter what the actual type is for a particular observer.

Structural types have the virtue of minimizing the interface between two things. In this case, the coupling consists of only a single method signature, rather than a type, such as a shared trait. A drawback of a structural type is that we still couple to a particular names. If a name is arbitrary, we don’t really care about its name so much as its intent. In our example of a single method, we can avoid coupling to the name using a function object instead. In fact, we did this in the section called “Overriding Abstract Types” in Chapter 6, Advanced Object-Oriented Programming In Scala.

On the other hand, if the name is a universal convention in some sense, then coupling to it has more merit. For example, foreach is very common name in the Scala library with a particular meaning, so defining a structural type based on foreach might be better for conveying intent to the user, rather than using an anonymous function of some kind.

Existential Types

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 particularly useful for interfacing to Java’s type system for three cases.

  1. The type parameters of generics are “erased” at the byte code level (called type erasure). For example, when a List[Int] is created, the Int type is not available in the byte code.
  2. You might encounter “raw” types, such as pre-Java 5 libraries where collections had no type parameters. (All type parameters are effectively Object).
  3. When Java uses wild cards in generics to express variance behavior when the generics are used, the actual type is unknown. (We discussed this earlier in the section called “Variance Under Inheritance”.)

Consider the case of pattern matching on List[A] objects. You might like to write code like the following

// code-examples/TypeSystem/existentials/type-erasure-wont-work.scala
// WARNINGS: Does not work as you might expect.

object ProcessList {
  def apply[B](list: List[B]) = list match {
    case lInt:    List[Int]    => // do something
    case lDouble: List[Double] => // do something
    case lString: List[String] => // do something
    case _                     => // default behavior
  }
}

If you compile this with the -unchecked flag on the JVM, you’ll get warnings that the type parameters like Int are unchecked, because of type erasure. Hence, we can’t distinguish between any of the list types shown.

The Manifests that we discussed previously won’t work either, because they can’t recover the erased type of B.

We’ve already learned that the best we can do in pattern matching is to focus on the fact that we have a list and not try to determine the “lost” type parameter for the list instance. For type safety, we have to specify that a list has a parameter, but since we don’t know what it is, we use the wild card _ character for the type parameter, e.g.,

case l: List[_] => // do something "generic" with the list

When used in a type context like this, the List[_] is actually shorthand for the existential type, List[T] forSome { type T }. This is the most general case. We’re saying the type parameter for the list could be any type. Here are some other examples which demonstrate the use of type bounds.

Table 12.2. Existential type examples.

Shorthand Full Description

List[_]

List[T] forSome { type T }

T can be any subtype of Any.

List[_ <: scala.actors.AbstractActor]

List[T] forSome { type T <: scala.actors.AbstractActor }

T can be any subtype of AbstractActor.

List[_ >: MyFancyActor <: scala.actors.AbstractActor]

List[T] forSome { type T >: MyFancyActor <: scala.actors.AbstractActor }

T can be any subtype of AbstractActor up to and including the subtype MyFancyActor.


If you think about how Scala syntax for generics is mapped to Java syntax, you might have noticed that an expression like java.util.List[_ <: scala.actors.AbstractActor] is structurally similar to the Java variance expression java.util.List<? extends scala.actors.AbstractActor>. In fact, they are the same declarations. Although we said that variance behavior in Scala is defined at the declaration site, you can use existential type expressions in Scala to define call-site variance behavior. It is not recommended, for the reasons discussed previously, but you have that option.

You won’t see the forSome existential type syntax very often in Scala code, because existential types exist primarily to support Java generics while preserving correctness in Scala’s type system. Type inference hides the details from us in most contexts. When working with Scala types, the other type constructs we have discussed in this chapter are preferred to existential types.

Infinite Data Structures and Laziness

We described lazy values in Chapter 8, Functional Programming in Scala. In functional languages that are lazy by default, like Haskell, laziness makes it easy to support infinite data structures.

For example, consider the following Scala method fib that calculates the Fibonacci number for n in the infinite Fibonacci sequence.

def fib(n: Int): Int = n match {
  case 0 | 1 => n
  case _ => fib(n-1) + fib(n-2)
}

If Scala were purely lazy, we could imagine a definition of the Fibonacci sequence like the following and it wouldn’t create an infinite loop.

fibonacci_sequence = for (i <- 0 to infinity) yield fib(i)

Scala isn’t lazy by default (and there is no infinity value or keyword…), but the library contains a Stream class that supports lazy evaluation and hence it can support infinite data structures. We’ll show an implementation of the Fibonacci sequence in a moment. First, here is a simpler example that uses streams to represent all positive integers, all positive odd integers, and all positive even integers.

// code-examples/TypeSystem/lazy/lazy-ints-script.scala

def from(n: Int): Stream[Int] = Stream.cons(n, from(n+1))

lazy val ints = from(0)
lazy val odds = ints.filter(_ % 2 == 1)
lazy val evens = ints.filter(_ % 2 == 0)

odds.take(10).print
evens.take(10).print

It produces this output.

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, Stream.empty
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, Stream.empty

The from method is recursive and it never terminates! We use it to define the ints by calling from(0). Streams.cons is an object with an apply method that is analogous to the :: (“cons”) method on List. It returns a new stream with the first argument as the head and the second argument, another stream, as the tail. The odds and evens infinite streams are computed by filtering ints.

Once we have defined the streams, the take method returns a new stream of the fixed size specified, 10 in this case. When we print this stream with the print method, it prints the 10 elements followed by Stream.empty when it hits the end of the stream.

Returning to the Fibonacci sequence, there is a famous definition using infinite, lazy sequences that exploits the “zip” operation (see, e.g., [Abelson1996]). Our discussion for Scala is adapted from [Ortiz2007].

// code-examples/TypeSystem/lazy/lazy-fibonacci-script.scala

lazy val fib: Stream[Int] =
  Stream.cons(0, Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)))

fib.take(10).print

It produces this output.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, Stream.empty

How does this work? Like our iterative definition at the start of this section, we explicitly specify the first two values, 0 and 1. The rest of the numbers are computed using zip, exploiting the fact that fib(n) = fib(n-1) + fib(n-2), for n > 1.

The call fib.zip(fib.tail) creates a new stream of tuples with the elements of fib in the first position of the tuple, and the elements of fib.tail in the second position of the tuple. To get back to a single integer for each position in the stream, we map the stream of tuples to a stream of Ints by adding the tuple elements. Here are the tuples calculated.

(0,1), (1,1), (1,2), (2,3), (3,5), (5,8), (8,13), (13, 21), (21, 34), ...

Note that each second element is the next number in the Fibonacci sequence after the first element in the tuple. Adding them we get the following.

1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Since we concatenate this stream after 0 and 1, we get the Fibonacci sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

Another lazy Scala type, albeit a finite one, is Range. Typically, you write literal ranges such as 1 to 1000. Range is lazy, so that very large ranges don’t consume too many resources. However, this feature can lead to subtle problems unless you are careful, as documented by [Smith2009b] and commenters. Using the example described there, consider this function for returning a Seq of three random integers.

// code-examples/TypeSystem/lazy/lazy-range-danger-script.scala

def mkRandomInts() = {
  val randInts = for {
    i <- 1 to 3
    val rand = i + (new scala.util.Random).nextInt
  } yield rand
  randInts
}
val ints1 = mkRandomInts

println("Calling first on ints1 Seq:")
for (i <- 1 to 3) {
  println( ints1.first)
}

val ints2 = ints1.toList
println("Calling first on List created from ints1 Seq:")
for (i <- 1 to 3) {
  println( ints2.first)
}

Here is the output from one run. The actual values will vary from run to run.

Calling first on ints1 Seq:
-1532554511
-1532939260
-1532939260
Calling first on List created from ints1 Seq:
-1537171498
-1537171498
-1537171498

Calling first on the sequence does not always return the same value! The reason is that the range at the beginning of the for comprehension effectively forces the whole sequence to be lazy. Hence, it is re-evaluated with each call to first and the first value in the sequence actually changes, since Random returns a different number each time (at least it will if there is a sufficient time delta between calls).

However, calling toList on the sequence forces it to evaluate the whole range and create a strict list.

Warning

Avoid using ranges in for (…) yield x constructs, while for (…) {…} alternatives are fine.

Finally, Scala version 2.8 will include a force method on all collections that will force them to be strict.

Recap and What’s Next

It’s important to remember that you don’t have to master the intricacies of Scala’s rich type system to use Scala effectively. As you use Scala more and more, mastering the type system will help you create powerful, sophisticated libraries that will accelerate your productivity.

The [ScalaSpec2009] describes the type system in formal detail. Like any specification, it can be difficult reading. The effort is worthwhile if you want a deep understanding of the type system. There are also a multitude of papers on Scala’s type system. You can find links to many of them on the official http://scala-lang.org website.

The next two chapters cover the pragmatics of application design and Scala’s development tools and libraries.

You must sign in or register before commenting