Parametric polymorphism

Parametric Polymorphism is a way to define types or functions that are generic over other types. The genericity can be expressed by using type variables for the parameter type, and by a mechanism to explicitly or implicitly replace the type variables with concrete types when necessary.

Write a small example for a type declaration that is parametric over another type, together with a short bit of code (and its type signature) that uses it. A good example is a container type, let's say a binary tree, together with some function that traverses the tree, say, a map-function that operates on every element of the tree.

This language feature only applies to statically-typed languages.

Ada

<lang ada>generic

  type Element_Type is private;

package Container is

  type Tree is tagged private;
  procedure Replace_All(The_Tree : in out Tree; New_Value : Element_Type);

private

  type Node;
  type Node_Access is access Node;
  type Tree tagged record
     Value : Element_type;
     Left  : Node_Access := null;
     Right : Node_Access := null;
  end record;

end Container;</lang> <lang ada>package body Container is

  procedure Replace_All(The_Tree : in out Tree; New_Value : Element_Type) is
  begin
     The_Tree.Value := New_Value;
     If The_Tree.Left /= null then
        The_Tree.Left.all.Replace_All(New_Value);
     end if;
     if The_tree.Right /= null then
        The_Tree.Right.all.Replace_All(New_Value);
     end if;
  end Replace_All;

end Container;</lang>

C++

<lang cpp>template<class T> class tree {

 T value;
 tree *left;
 tree *right;

public:

 void replace_all (T new_value);

};</lang>

For simplicity, we replace all values in the tree with a new value:

<lang cpp>template<class T> void tree<T>::replace_all (T new_value) {

 value = new_value;
 left->replace_all (new_value);
 right->replace_all (new_value);

}</lang>

C#

<lang csharp>namespace RosettaCode {

   class BinaryTree<T> {
       T value;
       BinaryTree<T> left;
       BinaryTree<T> right;

       public void ReplaceAll(T value) {
           this.value = value;
           if (left != null) {
               left.ReplaceAll(value);
           }
           if (right != null) {
               right.ReplaceAll(value);
           }
       }
   }

}</lang>

Sample that creates a tree to hold int values:

<lang csharp>namespace RosettaCode {

   class Program {
       static void Main(string[] args) {
           BinaryTree<int> tree = new BinaryTree<int>();

           tree.ReplaceAll(5);
       }
   }

}</lang>

Clean

<lang clean>::Tree a = Empty | Node a (Tree a) (Tree a)

mapTree :: (a -> b) (Tree a) -> (Tree b) mapTree f Empty = Empty mapTree f (Node x l r) = Node (f x) (mapTree f l) (mapTree f r)</lang>

A digression:
Note that for the most usefulness in practical programming, a map operation like this should not be defined with a separate name but rather as fmap in an instance of the Functor type class:
<lang clean>instance Functor Tree where fmap f Empty = Empty fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)</lang>
fmap can then be used exactly where mapTree can, but doing this also allows the use of Trees with other components which are parametric over any type which is a Functor. For example, this function will add 1 to any collection of any kind of number:
<lang clean>add1Everywhere :: (f a) -> (f a) | Functor f & Num a add1Everywhere nums = fmap (\x = x + 1) nums</lang>
If we have a tree of integers, i.e. f is Tree and a is Integer, then the type of add1Everywhere is Tree Integer -> Tree Integer.

Common Lisp

Common Lisp is not statically typed, but types can be defined which are parameterized over other types. In the following piece of code, a type pair is defined which accepts two (optional) type specifiers. An object is of type (pair :car car-type :cdr cdr-type) if an only if it is a cons whose car is of type car-type and whose cdr is of type cdr-type.

<lang lisp>(deftype pair (&key (car 't) (cdr 't))

 `(cons ,car ,cdr))</lang>

Example

> (typep (cons 1 2) '(pair :car number :cdr number))
T

> (typep (cons 1 2) '(pair :car number :cdr character))
NIL

D

D template can parametric by constant. <lang d>module parapoly ;

class ArrayTree(T, int LEN) {

 // template instantiation in alias
 alias ArrayTree!(T, LEN) ANode ;  
 const int length = LEN ;
 T[LEN] array ;
 ANode LHS, RHS ;
 this (T initvalue) { array[] = initvalue ; }
 void map(void delegate(T[]) dg) { 
   dg(array) ;
   if(LHS) LHS.map(dg) ; 
   if(RHS) RHS.map(dg) ; 
 }

}</lang> This is a using example. <lang d>module polytest ; import std.stdio ; import parapoly ;

//Instantiating an ArrayTree class of real(T) array, whose length(LEN) is 3. alias ArrayTree!(real, 3) VecT ;

void main() {

 VecT v = new VecT(0.01);
 // init an array tree.
 v.LHS = new VecT(1.11) ; v.LHS.LHS = new VecT(1.11) ; v.LHS.RHS = new VecT(1.12) ;
 v.RHS = new VecT(1.21) ; v.RHS.LHS = new VecT(1.21) ; v.RHS.RHS = new VecT(1.22) ;

 // do something start from root v
 v.map((real[] x){writefln(x) ;} ) ;
 real new_value = 0.9L ; 
 v.map((real[] x){x[] = new_value ;} ) ;
 writefln() ;
 v.map((real[] x){writefln(x) ;} ) ;

}</lang>

E

While E itself does not do static (before evaluation) type checking, E does have guards which form a runtime type system, and has typed collections in the standard library. Here, we implement a typed tree, and a guard which accepts trees of a specific type.

(Note: Like some other examples here, this is an incomplete program in that the tree provides no way to insert or delete nodes.)

(Note: The guard definition is arguably messy boilerplate; future versions of E may provide a scheme where the interface expression can itself be used to describe parametricity, and message signatures using the type parameter, but this has not been implemented or fully designed yet. Currently, this example is more of “you can do it if you need to” than something worth doing for every data structure in your program.)

<lang e>interface TreeAny guards TreeStamp {} def Tree {

   to get(Value) {
       def Tree1 {
           to coerce(specimen, ejector) {
               def tree := TreeAny.coerce(specimen, ejector)
               if (tree.valueType() != Value) {
                   throw.eject(ejector, "Tree value type mismatch")
               }
               return tree
           }
       }
       return Tree1
   }

}

def makeTree(T, var value :T, left :nullOk[Tree[T]], right :nullOk[Tree[T]]) {

   def tree implements TreeStamp {
       to valueType() { return T }
       to map(f) {
           value := f(value)  # the declaration of value causes this to be checked
           if (left != null) {
               left.map(f)
           }
           if (right != null) {
               right.map(f)
           }
       }
   }
   return tree

}</lang>

<lang e>? def t := makeTree(int, 0, null, null)

value: <tree>

? t :Tree[String]

problem: Tree value type mismatch

? t :Tree[Int]

problem: Failed: Undefined variable: Int

? t :Tree[int]

value: <tree></lang>

Haskell

<lang haskell>data Tree a = Empty | Node a (Tree a) (Tree a)

mapTree :: (a -> b) -> Tree a -> Tree b mapTree f Empty = Empty mapTree f (Node x l r) = Node (f x) (mapTree f l) (mapTree f r)</lang>

A digression:
Note that for the most usefulness in practical programming, a map operation like this should not be defined with a separate name but rather as fmap in an instance of the Functor type class:
<lang haskell>instance Functor Tree where fmap f Empty = Empty fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)</lang>
fmap can then be used exactly where mapTree can, but doing this also allows the use of Trees with other components which are parametric over any type which is a Functor. For example, this function will add 1 to any collection of any kind of number:
<lang haskell>add1Everywhere :: (Functor f, Num a) => f a -> f a add1Everywhere nums = fmap (\x -> x + 1) nums</lang>
If we have a tree of integers, i.e. f is Tree and a is Integer, then the type of add1Everywhere is Tree Integer -> Tree Integer.

Java

Following the C++ example: <lang java>public class Tree<T>{ private T value; private Tree<T> left; private Tree<T> right;

public void replaceAll(T value){ this.value = value; if(left != null) left.replaceAll(value); if(right != null) right.replaceAll(value); } }</lang>

OCaml

<lang ocaml>type 'a tree = Empty | Node of 'a * 'a tree * 'a tree

(** val map_tree : ('a -> 'b) -> 'a tree -> 'b tree *) let rec map_tree f = function

 | Empty        -> Empty
 | Node (x,l,r) -> Node (f x, map_tree f l, map_tree f r)</lang>

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 Tree, [+A]. The plus sign indicates that Tree is co-variant on A. That means Tree[X] will be a subtype of Tree[Y] if X is a subtype of Y. 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 t is of type Tree[Manager], and since Manager is a subclass of Employee, then Tree[Manager] is a subtype of Tree[Employee].

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 map is expecting a function from Manager into something, but toName is a function of Employee into String, and Employee is a supertype, not a subtype, of Manager. 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 T1, which happens to be the type of the argument of the function. In other words, it tell us that, Employee => String is a subtype of Manager => String, because Employee is a supertype of Manager. While the concept of contra-variance is not intuitive, it should be clear to anyone that toName can handle arguments of type Manager, but, were not for the contra-variance, it would not be usable with a Tree[Manager].

Let's add another method to Tree 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 find is [B >: A]. That means the type is some B, as long as that B is a supertype of A. If I tried to declare what: A, 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 find receiving an argument of type Employee, even though the tree it was defined on is of type Manager. The co-variance of Tree means a situation such as this is possible.

There is also an operator <:, with the opposite meaning of >:.

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 DFA would need to define Element. 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.

Standard ML

<lang sml>datatype 'a tree = Empty | Node of 'a * 'a tree * 'a tree

(** val map_tree = fn : ('a -> 'b) -> 'a tree -> 'b tree *) fun map_tree f Empty = Empty

 | map_tree f (Node (x,l,r)) = Node (f x, map_tree f l, map_tree f r)</lang>

Ursala

Types are first class entities and functions to construct or operate on them may be defined routinely. A parameterized binary tree type can be defined using a syntax for anonymous recursion in type expressions as in this example, <lang Ursala>binary_tree_of "node-type" = "node-type"%hhhhWZAZ</lang> or by way of a recurrence solved using a fixed point combinator imported from a library as shown below. <lang Ursala>#import tag

fix general_type_fixer 1

binary_tree_of "node-type" = ("node-type",(binary_tree_of "node-type")%Z)%drWZwlwAZ</lang> (The %Z type operator constructs a "maybe" type, i.e., the free union of its operand type with the null value. Others shown above are standard stack manipulation primitives, e.g. d (dup) and w (swap), used to build the type expression tree.) At the other extreme, one may construct an equivalent parameterized type in point-free form. <lang Ursala>binary_tree_of = %-hhhhWZAZ</lang> A mapping combinator over this type can be defined with pattern matching like this <lang Ursala>binary_tree_map "f" = ~&a^& ^A/"f"@an ~&amPfamPWB</lang> or in point free form like this. <lang Ursala>binary_tree_map = ~&a^&+ ^A\~&amPfamPWB+ @an</lang> Here is a test program defining a type of binary trees of strings, and a function that concatenates each node with itself. <lang Ursala>string_tree = binary_tree_of %s

x = 'foo': ('bar': (),'baz': ())

cast string_tree

example = (binary_tree_map "s". "s"--"s") x</lang> Type signatures are not necessarily associated with function declarations, but have uses in the other contexts such as assertions and compiler directives (e.g., #cast). Here is the output.

'foofoo': ('barbar': (),'bazbaz': ())