Parametric polymorphism

Parametric Polymorphism is a way to define types that are generic over other types (therefore, sometimes this feature is called generic programming). 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.

C plus plus

template<class T> 
class tree
{
  T value;
  tree *left;
  tree *right;
public:
  void replace_all (T new_value);
};

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

template<class T>
void tree<T>::replace_all (T new_value)
{
  value = new_value;
  left->replace_all (new_value);
  right->replace_all (new_value);
}

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)

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)