Scala Note 24: Generic Types and Methods

Scala does not allow one to parameterize objects with types, but we can define a generic class.
Type parameters are arbitrary names. They are enclosed in brackets instead of parentheses.
It is possible to parameterize classes and methods with types.

The method parameters are called polymorphic. Generic methods are also called
polymorphic(means having many forms).

For example,

abstract class Stack[A] {
def push(x: A): Stack[A] = new NonEmptyStack[A](x, this)
def isEmpty: Boolean
def top: A
def pop: Stack[A]

}

class EmptyStack[A] extends Stack[A] {
def isEmpty = true
def top = error("EmptyStack.top")
def pop = error("EmptyStack.pop")

}

def isPrefix[A](p: Stack[A], s: Stack[A]): Boolean = {
p.isEmpty ||
p.top == s.top && isPrefix[A](p.pop, s.pop)

}

val s1 = new EmptyStack[String].push("abc")
val s2 = new EmptyStack[String].push("abx").push(s1.top)

println(isPrefix[String](s1, s2))

Local Type Inference:

The information in a type parameter is redundant, because the correct parameter type can also be determined by inspecting the function's value parameters or expected result type.
In the example above, one could have written isPrefix(s1, s2) and the missing type argument [String] would have been inserted by the type inferencer.


Type Parameter Bounds

trait Set[A <: U] ...
class EmptySet[A <: U] ...

class NonEmptySet[A <: U] ...

The parameter declaration A <: U introduces A as a type parameter which must be a subtype of U.
Symmetrical to this are lower bounds in Scala. A >: U, the type A is restricted to range only over super types of type U.

Variance Annotations

In Scala, generic types have by default non-variant subtyping.  However, we can enforce co-variant subtyping of stacks by changing the first line of the definition of class Stack as follows.


class Stack[+A] {

Prefixing a formal type parameter with a + indicates that subtyping is covariant in that parameter.
For example, T a subtype of type A would imply that Stack[T] is a subtype of Stack[A]

Scala uses a conservative approximation to verify soundness of variance annotations.
A covariant type parameter of a class may only appear in co-variant positions
inside the class. Among the co-variant positions are the types of values in the
class, the result types of methods in the class, and type arguments to other covariant
types. Not co-variant are types of formal method parameters. Hence, the following
class definition would have been rejected.

class Array[+A] {
       def apply(index: Int): A
       def update(index: Int, elem: A)
                                          ^ covariant type parameter A
                                         appears in contravariant position.

}


Contra-variant Functions

val f: (AnyRef => Int) = x => x.hashCode()
val g: (String => Int) = f

g("abc")

Function subtyping is contra-variant in its argument type whereas it is covariant in

its result type. In short, S =>T is a subtype of S'=>T', provided S' is a subtype of S
and T is a subtype of T'.