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.

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;

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

C++

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)

Java

Following the C++ example:

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);
	}
}

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)