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++

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

D

D template can parametric by constant.

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

This is a using example.

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

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)

Standard ML

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)