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.
You are encouraged to solve this task according to the task description, using any language you may know.
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)