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>