Parametric polymorphism: Difference between revisions
Content added Content deleted
m (omit JavaScript) |
(Added Scala) |
||
Line 241: | Line 241: | ||
| Empty -> Empty |
| Empty -> Empty |
||
| Node (x,l,r) -> Node (f x, map_tree f l, map_tree f r)</lang> |
| Node (x,l,r) -> Node (f x, map_tree f l, map_tree f r)</lang> |
||
=={{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><:</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. |
|||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |