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