Parametric polymorphism: Difference between revisions

=={{header|Scala}}==

There's much to be said about parametric polymorphism in Scala. Let's first see

the example in question:

<lang scala>case class Tree[+A](value: A, left: Option[Tree[A]], right: Option[Tree[A]]) {

def map[B](f: A => B): Tree[B] =

Tree(f(value), left map (_.map(f)), right map (_.map(f)))

}</lang>

Note that the type parameter of the class <tt>Tree</tt>, <tt>[+A]</tt>. The

plus sign indicates that <tt>Tree</tt> is ''co-variant'' on <tt>A</tt>. That means <tt>Tree[X]</tt>

will be a subtype of <tt>Tree[Y]</tt> if <tt>X</tt> is a subtype of <tt>Y</tt>. For example:

<lang scala>class Employee(val name: String)

class Manager(name: String) extends Employee(name)

val t = Tree(new Manager("PHB"), None, None)

val t2: Tree[Employee] = t</lang>

The second assignment is legal because <tt>t</tt> is of type <tt>Tree[Manager]</tt>, and since

<tt>Manager</tt> is a subclass of <tt>Employee</tt>, then <tt>Tree[Manager]</tt> is a subtype of

<tt>Tree[Employee]</tt>.

Another possible variance is the ''contra-variance''. For instance, consider the following example:

<lang scala>def toName(e: Employee) = e.name

val treeOfNames = t.map(toName)</lang>

This works, even though <tt>map</tt> is expecting a function from <tt>Manager</tt> into something,

but <tt>toName</tt> is a function of <tt>Employee</tt> into <tt>String</tt>, and <tt>Employee</tt>

is a supertype, not a subtype, of <tt>Manager</tt>. It works because functions have the following

definition in Scala:

<lang scala>trait Function1[-T1, +R]</lang>

The minus sign indicates that this trait is ''contra-variant'' in <tt>T1</tt>, which happens to be

the type of the argument of the function. In other words, it tell us that, <tt>Employee => String</tt>

is a ''subtype'' of <tt>Manager => String</tt>, because <tt>Employee</tt> is a ''supertype'' of

<tt>Manager</tt>. While the concept of contra-variance is not intuitive, it should be clear to anyone

that <tt>toName</tt> can handle arguments of type <tt>Manager</tt>, but, were not for the contra-variance,

it would ''not'' be usable with a <tt>Tree[Manager]</tt>.

Let's add another method to <tt>Tree</tt> to see another concept:

<lang scala>case class Tree[+A](value: A, left: Option[Tree[A]], right: Option[Tree[A]]) {

def map[B](f: A => B): Tree[B] =

Tree(f(value), left map (_.map(f)), right map (_.map(f)))

def find[B >: A](what: B): Boolean =

(value == what) || left.map(_.find(what)).getOrElse(false) || right.map(_.find(what)).getOrElse(false)

}</lang>

The type parameter of <tt>find</tt> is <tt>[B >: A]</tt>. That means the type is some <tt>B</tt>, as long

as that <tt>B</tt> is a supertype of <tt>A</tt>. If I tried to declare <tt>what: A</tt>, Scala would not

accept it. To understand why, let's consider the following code:

<lang scala>if (t2.find(new Employee("Dilbert")))

println("Call Catbert!")</lang>

Here we have <tt>find</tt> receiving an argument of type <tt>Employee</tt>, even though the tree

it was defined on is of type <tt>Manager</tt>. The co-variance of <tt>Tree</tt> means a situation

such as this is possible.

There is also an operator <tt>&lt;:</tt>, with the opposite meaning of <tt>>:</tt>.

Finally, Scala also allows abstract types. Abtract types are similar to abstract methods: they have

to be defined when a class is inherited. One simple example would be:

<lang scala>trait DFA {

type Element

val map = new collection.mutable.HashMap[Element, DFA]()

}</lang>

A concrete class wishing to inherit from <tt>DFA</tt> would need to define <tt>Element</tt>. Abstract

types aren't all that different from type parameters. Mainly, they ensure that the type will be

selected in the definition site (the declaration of the concrete class), and not at the usage site

(instantiation of the concrete class). The difference is mainly one of style, though.