Parametric polymorphism

Parametric polymorphism
You are encouraged to solve this task according to the task description, using any language you may know.

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>

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>

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>

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>

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>