Parametric polymorphism: Difference between revisions
No edit summary |
(→{{header|C sharp|C#}}: Fix compilation error in main program, cannot implicitly convert type BinaryTree<int> to type BinaryTree<U>) |
||
| Line 140: | Line 140: | ||
class Program { |
class Program { |
||
static void Main(string[] args) { |
static void Main(string[] args) { |
||
BinaryTree< |
BinaryTree<int> b = new BinaryTree<int>(6); |
||
b.left = new BinaryTree<int>(5); |
b.left = new BinaryTree<int>(5); |
||
b.right = new BinaryTree<int>(7); |
b.right = new BinaryTree<int>(7); |
||
BinaryTree< |
BinaryTree<double> b2 = b.Map(x => x * 10.0); |
||
} |
} |
||
} |
} |
||
Revision as of 03:09, 3 March 2016
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
If the goal is to separate algorithms from types at compile type, C may do it by macros. Here's sample code implementing binary tree with node creation and insertion:<lang C>#include <stdio.h>
- include <stdlib.h>
- define decl_tree_type(T) \
typedef struct node_##T##_t node_##T##_t, *node_##T; \
struct node_##T##_t { node_##T left, right; T value; }; \
\
node_##T node_##T##_new(T v) { \
node_##T node = malloc(sizeof(node_##T##_t)); \
node->value = v; \
node->left = node->right = 0; \
return node; \
} \
node_##T node_##T##_insert(node_##T root, T v) { \
node_##T n = node_##T##_new(v); \
while (root) { \
if (root->value < n->value) \
if (!root->left) return root->left = n; \
else root = root->left; \
else \
if (!root->right) return root->right = n; \
else root = root->right; \
} \
return 0; \
}
- define tree_node(T) node_##T
- define node_insert(T, r, x) node_##T##_insert(r, x)
- define node_new(T, x) node_##T##_new(x)
decl_tree_type(double); decl_tree_type(int);
int main() {
int i;
tree_node(double) root_d = node_new(double, (double)rand() / RAND_MAX);
for (i = 0; i < 10000; i++)
node_insert(double, root_d, (double)rand() / RAND_MAX);
tree_node(int) root_i = node_new(int, rand());
for (i = 0; i < 10000; i++)
node_insert(int, root_i, rand());
return 0;
}</lang> Comments: It's ugly looking, but it gets the job done. It has the drawback that all methods need to be re-created for each tree data type used, but hey, C++ template does that, too.
Arguably more interesting is run time polymorphism, which can't be trivially done; if you are confident in your coding skill, you could keep track of data types and method dispatch at run time yourself -- but then, you are probably too confident to not realize you might be better off using some higher level languages.
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; if (left != NULL) left->replace_all (new_value); if (right != NULL) right->replace_all (new_value);
}</lang>
C#
<lang csharp>namespace RosettaCode {
class BinaryTree<T> {
public T value;
public BinaryTree<T> left;
public BinaryTree<T> right;
public BinaryTree(T value) {
this.value = value;
}
public BinaryTree Map(Func<T,U> f) {
BinaryTree Tree = new BinaryTree(f(this.value));
if (left != null) {
Tree.left = left.Map(f);
}
if (right != null) {
Tree.right = right.Map(f);
}
return Tree;
}
}
}</lang>
Sample that creates a tree to hold int values:
<lang csharp>namespace RosettaCode {
class Program {
static void Main(string[] args) {
BinaryTree<int> b = new BinaryTree<int>(6);
b.left = new BinaryTree<int>(5);
b.right = new BinaryTree<int>(7);
BinaryTree<double> b2 = b.Map(x => x * 10.0);
}
}
}</lang>
Ceylon
<lang ceylon>class BinaryTree(shared Data data, shared BinaryTree? left = null, shared BinaryTree? right = null) {
shared BinaryTree<NewData> myMap<NewData>(NewData f(Data d)) => BinaryTree { data = f(data); left = left?.myMap(f); right = right?.myMap(f); }; }
shared void run() {
value tree1 = BinaryTree { data = 3; left = BinaryTree { data = 4; }; right = BinaryTree { data = 5; left = BinaryTree { data = 6; }; }; };
tree1.myMap(print); print("");
value tree2 = tree1.myMap((x) => x * 333.33); tree2.myMap(print); }</lang>
Clean
<lang clean>::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>
A digression:
Note that for the most usefulness in practical programming, a map operation like this should not be defined with a separate name but rather as
fmapin an instance of theFunctortype class:<lang clean>instance Functor Tree where fmap f Empty = Empty fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)</lang>
fmapcan then be used exactly wheremapTreecan, but doing this also allows the use ofTrees with other components which are parametric over any type which is a Functor. For example, this function will add 1 to any collection of any kind of number:<lang clean>add1Everywhere :: (f a) -> (f a) | Functor f & Num a add1Everywhere nums = fmap (\x = x + 1) nums</lang>
If we have a tree of integers, i.e. f is
Treeand a isInteger, then the type ofadd1EverywhereisTree Integer -> Tree Integer.
Common Lisp
Common Lisp is not statically typed, but types can be defined which are parameterized over other types. In the following piece of code, a type pair is defined which accepts two (optional) type specifiers. An object is of type (pair :car car-type :cdr cdr-type) if an only if it is a cons whose car is of type car-type and whose cdr is of type cdr-type.
<lang lisp>(deftype pair (&key (car 't) (cdr 't))
`(cons ,car ,cdr))</lang>
Example
> (typep (cons 1 2) '(pair :car number :cdr number)) T
> (typep (cons 1 2) '(pair :car number :cdr character)) NIL
D
<lang d>class ArrayTree(T, uint N) {
T[N] data; typeof(this) left, right;
this(T initValue) { this.data[] = initValue; }
void tmap(const void delegate(ref typeof(data)) dg) {
dg(this.data);
if (left) left.tmap(dg);
if (right) right.tmap(dg);
}
}
void main() { // Demo code.
import std.stdio;
// Instantiate the template ArrayTree of three doubles. alias AT3 = ArrayTree!(double, 3);
// Allocate the tree root. auto root = new AT3(1.00);
// Add some nodes. root.left = new AT3(1.10); root.left.left = new AT3(1.11); root.left.right = new AT3(1.12);
root.right = new AT3(1.20); root.right.left = new AT3(1.21); root.right.right = new AT3(1.22);
// Now the tree has seven nodes.
// Show the arrays of the whole tree.
//root.tmap(x => writefln("%(%.2f %)", x));
root.tmap((ref x) => writefln("%(%.2f %)", x));
// Modify the arrays of the whole tree.
//root.tmap((x){ x[] += 10; });
root.tmap((ref x){ x[] += 10; });
// Show the arrays of the whole tree again.
writeln();
//root.tmap(x => writefln("%(%.2f %)", x));
root.tmap((ref x) => writefln("%(%.2f %)", x));
}</lang>
- Output:
1.00 1.00 1.00 1.10 1.10 1.10 1.11 1.11 1.11 1.12 1.12 1.12 1.20 1.20 1.20 1.21 1.21 1.21 1.22 1.22 1.22 11.00 11.00 11.00 11.10 11.10 11.10 11.11 11.11 11.11 11.12 11.12 11.12 11.20 11.20 11.20 11.21 11.21 11.21 11.22 11.22 11.22
Dart
<lang dart>class TreeNode<T> {
T value;
TreeNode<T> left;
TreeNode<T> right;
TreeNode(this.value);
TreeNode map(T f(T t)) {
var node = new TreeNode(f(value));
if(left != null) {
node.left = left.map(f);
}
if(right != null) {
node.right = right.map(f);
}
return node;
}
void forEach(void f(T t)) {
f(value);
if(left != null) {
left.forEach(f);
}
if(right != null) {
right.forEach(f);
}
}
}
void main() {
TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.right = new TreeNode(4);
print('first tree');
root.forEach(print);
var newRoot = root.map((t) => t * 222);
print('second tree');
newRoot.forEach(print);
}</lang>
- Output:
first tree 1 2 4 3 second tree 222 444 888 666
E
While E itself does not do static (before evaluation) type checking, E does have guards which form a runtime type system, and has typed collections in the standard library. Here, we implement a typed tree, and a guard which accepts trees of a specific type.
(Note: Like some other examples here, this is an incomplete program in that the tree provides no way to insert or delete nodes.)
(Note: The guard definition is arguably messy boilerplate; future versions of E may provide a scheme where the interface expression can itself be used to describe parametricity, and message signatures using the type parameter, but this has not been implemented or fully designed yet. Currently, this example is more of “you can do it if you need to” than something worth doing for every data structure in your program.)
<lang e>interface TreeAny guards TreeStamp {} def Tree {
to get(Value) {
def Tree1 {
to coerce(specimen, ejector) {
def tree := TreeAny.coerce(specimen, ejector)
if (tree.valueType() != Value) {
throw.eject(ejector, "Tree value type mismatch")
}
return tree
}
}
return Tree1
}
}
def makeTree(T, var value :T, left :nullOk[Tree[T]], right :nullOk[Tree[T]]) {
def tree implements TreeStamp {
to valueType() { return T }
to map(f) {
value := f(value) # the declaration of value causes this to be checked
if (left != null) {
left.map(f)
}
if (right != null) {
right.map(f)
}
}
}
return tree
}</lang>
<lang e>? def t := makeTree(int, 0, null, null)
- value: <tree>
? t :Tree[String]
- problem: Tree value type mismatch
? t :Tree[Int]
- problem: Failed: Undefined variable: Int
? t :Tree[int]
- value: <tree></lang>
F#
<lang fsharp>
namespace RosettaCode
type BinaryTree<'T> =
| Element of 'T
| Tree of 'T * BinaryTree<'T> * BinaryTree<'T>
member this.Map(f) =
match this with
| Element(x) -> Element(f x)
| Tree(x,left,right) -> Tree((f x), left.Map(f), right.Map(f))
</lang>
We can test this binary tree like so: <lang fsharp>
let t1 = Tree(2, Element(1), Tree(4,Element(3),Element(5)) ) let t2 = t1.Map(fun x -> x * 10)
</lang>
Go
The parametric function in this example is the function average. It's type parameter is the interface type intCollection, and its logic uses the polymorphic function mapElements. In Go terminology, average is an ordinary function whose parameter happens to be of interface type. Code inside of average is ordinary code that just happens to call the mapElements method of its parameter. This code accesses the underlying static type only through the interface and so has no knowledge of the details of the static type or even which static type it is dealing with.
Function main creates objects t1 and t2 of two different static types, binaryTree an bTree. Both types implement the interface intCollection. t1 and t2 have different static types, but when they are passed to average, they are bound to parameter c, of interface type, and their static types are not visible within average.
Implementation of binaryTree and bTree is dummied, but you can see that implementation of average of binaryTree contains code specific to its representation (left, right) and that implementation of bTree contains code specific to its representation (buckets.) <lang go>package main
import "fmt"
func average(c intCollection) float64 {
var sum, count int
c.mapElements(func(n int) {
sum += n
count++
})
return float64(sum) / float64(count)
}
func main() {
t1 := new(binaryTree)
t2 := new(bTree)
a1 := average(t1)
a2 := average(t2)
fmt.Println("binary tree average:", a1)
fmt.Println("b-tree average:", a2)
}
type intCollection interface {
mapElements(func(int))
}
type binaryTree struct {
// dummy representation details left, right bool
}
func (t *binaryTree) mapElements(visit func(int)) {
// dummy implementation
if t.left == t.right {
visit(3)
visit(1)
visit(4)
}
}
type bTree struct {
// dummy representation details buckets int
}
func (t *bTree) mapElements(visit func(int)) {
// dummy implementation
if t.buckets >= 0 {
visit(1)
visit(5)
visit(9)
}
}</lang> Output:
binary tree average: 2.6666666666666665 b-tree average: 5
Groovy
(more or less)
Solution: <lang groovy>class Tree<T> {
T value
Tree<T> left
Tree<T> right
Tree(T value = null, Tree<T> left = null, Tree<T> right = null) {
this.value = value
this.left = left
this.right = right
}
void replaceAll(T value) {
this.value = value
left?.replaceAll(value)
right?.replaceAll(value)
}
}</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>
A digression:
Note that for the most usefulness in practical programming, a map operation like this should not be defined with a separate name but rather as
fmapin an instance of theFunctortype class:<lang haskell>instance Functor Tree where fmap f Empty = Empty fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)</lang>
fmapcan then be used exactly wheremapTreecan, but doing this also allows the use ofTrees with other components which are parametric over any type which is a Functor. For example, this function will add 1 to any collection of any kind of number:<lang haskell>add1Everywhere :: (Functor f, Num a) => f a -> f a add1Everywhere nums = fmap (\x -> x + 1) nums</lang>
If we have a tree of integers, i.e. f is
Treeand a isInteger, then the type ofadd1EverywhereisTree Integer -> Tree Integer.
Inform 7
Phrases (the equivalent of global functions) can be defined with type parameters: <lang inform7>Polymorphism is a room.
To find (V - K) in (L - list of values of kind K): repeat with N running from 1 to the number of entries in L: if entry N in L is V: say "Found [V] at entry [N] in [L]."; stop; say "Did not find [V] in [L]."
When play begins: find "needle" in {"parrot", "needle", "rutabaga"}; find 6 in {2, 3, 4}; end the story.</lang>
Inform 7 does not allow user-defined parametric types. Some built-in types can be parameterized, though: <lang inform7>list of numbers relation of texts to rooms object based rulebook producing a number description of things activity on things number valued property text valued table column phrase (text, text) -> number</lang>
Icon and Unicon
Like PicoLisp, Icon and Unicon are dynamically typed and hence inherently polymorphic. Here's an example that can apply a function to the nodes in an n-tree regardless of the type of each node. It is up to the function to decide what to do with a given type of node. Note that the nodes do no even have to be of the same type.
<lang unicon>procedure main()
bTree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]] mapTree(bTree, write) bTree := [1, ["two", ["four", [7]], [5]], [3, ["six", ["eight"], [9]]]] mapTree(bTree, write)
end
procedure mapTree(tree, f)
every f(\tree[1]) | mapTree(!tree[2:0], f)
end</lang>
J
In J, all functions are generic over other types.
Alternatively, J is statically typed in the sense that it supports only one data type (the array), though of course inspecting a value can reveal additional details (such as: is it an array of numbers?)
(That said, note that J also supports some types which are not, strictly speaking, data. These are the verb, adverb and conjunction types. To fit this nomenclature, data is of type "noun". Also, nouns have some additional taxonomy which is beyond the scope of this task.)
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>
Mercury
<lang mercury>:- type tree(A) ---> empty ; node(A, tree(A), tree(A)).
- - func map(func(A) = B, tree(A)) = tree(B).
map(_, empty) = empty. map(F, node(A, Left, Right)) = node(F(A), map(F, Left), map(F, Right)).</lang>
Nim
<lang nim>type Tree[T] = ref object
value: T left, right: Tree[T]</lang>
Objective-C
<lang objc>@interface Tree<T> : NSObject {
T value; Tree<T> *left; Tree<T> *right;
}
- (void)replaceAll:(T)v; @end
@implementation Tree - (void)replaceAll:(id)v {
value = v; [left replaceAll:v]; [right replaceAll:v];
} @end</lang> Note that the generic type variable is only used in the declaration, but not in the implementation.
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>
Perl 6
<lang perl6>role BinaryTree[::T] {
has T $.value; has BinaryTree[T] $.left; has BinaryTree[T] $.right;
method replace-all(T $value) {
$!value = $value;
$!left.replace-all($value) if $!left.defined;
$!right.replace-all($value) if $!right.defined;
}
}
class IntTree does BinaryTree[Int] { }
my IntTree $it .= new(value => 1,
left => IntTree.new(value => 2),
right => IntTree.new(value => 3));
$it.replace-all(42); say $it.perl;</lang>
- Output:
IntTree.new(value => 42, left => IntTree.new(value => 42, left => BinaryTree[T], right => BinaryTree[T]), right => IntTree.new(value => 42, left => BinaryTree[T], right => BinaryTree[T]))
PicoLisp
PicoLisp is dynamically-typed, so in principle every function is polymetric over its arguments. It is up to the function to decide what to do with them. A function traversing a tree, modifying the nodes in-place (no matter what the type of the node is): <lang PicoLisp>(de mapTree (Tree Fun)
(set Tree (Fun (car Tree))) (and (cadr Tree) (mapTree @ Fun)) (and (cddr Tree) (mapTree @ Fun)) )</lang>
Test:
(balance 'MyTree (range 1 7)) # Create a tree of numbers
-> NIL
: (view MyTree T) # Display it
7
6
5
4
3
2
1
-> NIL
: (mapTree MyTree inc) # Increment all nodes
-> NIL
: (view MyTree T) # Display the tree
8
7
6
5
4
3
2
-> NIL
: (balance 'MyTree '("a" "b" "c" "d" "e" "f" "g")) # Create a tree of strings
-> NIL
: (view MyTree T) # Display it
"g"
"f"
"e"
"d"
"c"
"b"
"a"
-> NIL
: (mapTree MyTree uppc) # Convert all nodes to upper case
-> NIL
: (view MyTree T) # Display the tree
"G"
"F"
"E"
"D"
"C"
"B"
"A"
-> NILRacket
Typed Racket has parametric polymorphism:
<lang racket>
- lang typed/racket
(define-type (Tree A) (U False (Node A)))
(struct: (A) Node
([val : A] [left : (Tree A)] [right : (Tree A)]) #:transparent)
(: tree-map (All (A B) (A -> B) (Tree A) -> (Tree B))) (define (tree-map f tree)
(match tree
[#f #f]
[(Node val left right)
(Node (f val) (tree-map f left) (tree-map f right))]))
- unit tests
(require typed/rackunit) (check-equal?
(tree-map add1 (Node 5 (Node 3 #f #f) #f)) (Node 6 (Node 4 #f #f) #f))
</lang>
REXX
This REXX programming example is modeled after the D example. <lang rexx>/*REXX program demonstrates a method of parametric polymorphism in REXX.*/ call newRoot 1.00, 3 /*new root and indicate 3 stems. */
/* [↓] no need to label the stems*/
call addStem 1.10 /*new stem and its initial value.*/ call addStem 1.11 /* " " " " " " */ call addStem 1.12 /* " " " " " " */ call addStem 1.20 /* " " " " " " */ call addStem 1.21 /* " " " " " " */ call addStem 1.22 /* " " " " " " */ call sayNodes /*display nicely formatted values*/ call modRoot 50 /*MOD will add 50 to all stems. */ call sayNodes /*display nicely formatted values*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────MODROOT─────────────────────────────*/ modRoot: do j=1 for nodes /*traipse through all the nodes. */
do k=1 for stems; _=root.j.k; ?=datatype(_,'N')
if ? then root.j.k=_+arg(1) /*can stem be added to?*/
end /*k*/ /* [↑] only add if it's numeric.*/
end /*j*/
return /*──────────────────────────────────NEWROOT─────────────────────────────*/ newRoot: stems=arg(2); nodes=-1; /*set NODES to a kind of "null". */ call addStem copies('─',9); call addStem arg(1) return /*──────────────────────────────────SAYNODES────────────────────────────*/ sayNodes: say; do j=0 to nodes; _= /*each node gets shown*/
do k=1 for stems; _=_ right(root.j.k,9); end /*k*/
say substr(_,2) /*ignore the 1st blank*/
end /*j*/
say left(, stems*9+stems) || '('nodes" nodes)" /*also show # of nodes*/ return /*──────────────────────────────────ADDSTEM─────────────────────────────*/ addStem: nodes=nodes+1; do j=1 for stems; root.nodes.j=arg(1); end /*j*/ return</lang> output
───────── ───────── ─────────
1.00 1.00 1.00
1.10 1.10 1.10
1.11 1.11 1.11
1.12 1.12 1.12
1.20 1.20 1.20
1.21 1.21 1.21
1.22 1.22 1.22
(7 nodes)
───────── ───────── ─────────
51.00 51.00 51.00
51.10 51.10 51.10
51.11 51.11 51.11
51.12 51.12 51.12
51.20 51.20 51.20
51.21 51.21 51.21
51.22 51.22 51.22
(7 nodes)
Rust
<lang rust>struct TreeNode<T> {
value: T, left: Option<Box<TreeNode<T>>>, right: Option<Box<TreeNode<T>>>,
}
impl <T> TreeNode<T> {
fn my_map<U,F>(&self, f: &F) -> TreeNode where
F: Fn(&T) -> U {
TreeNode {
value: f(&self.value),
left: match self.left {
None => None,
Some(ref n) => Some(Box::new(n.my_map(f))),
},
right: match self.right {
None => None,
Some(ref n) => Some(Box::new(n.my_map(f))),
},
}
}
}
fn main() {
let root = TreeNode {
value: 3,
left: Some(Box::new(TreeNode {
value: 55,
left: None,
right: None,
})),
right: Some(Box::new(TreeNode {
value: 234,
left: Some(Box::new(TreeNode {
value: 0,
left: None,
right: None,
})),
right: None,
})),
};
root.my_map(&|x| { println!("{}" , x)});
println!("---------------");
let new_root = root.my_map(&|x| *x as f64 * 333.333f64);
new_root.my_map(&|x| { println!("{}" , x) });
}</lang>
Scala
There's much to be said about parametric polymorphism in Scala. Let's first see the example in question:
<lang scala>case class Tree[+A](value: A, left: Option[Tree[A]], right: Option[Tree[A]]) {
def map[B](f: A => B): Tree[B] = Tree(f(value), left map (_.map(f)), right map (_.map(f)))
}</lang>
Note that the type parameter of the class Tree, [+A]. The plus sign indicates that Tree is co-variant on A. That means Tree[X] will be a subtype of Tree[Y] if X is a subtype of Y. For example:
<lang scala>class Employee(val name: String) class Manager(name: String) extends Employee(name)
val t = Tree(new Manager("PHB"), None, None) val t2: Tree[Employee] = t</lang>
The second assignment is legal because t is of type Tree[Manager], and since Manager is a subclass of Employee, then Tree[Manager] is a subtype of Tree[Employee].
Another possible variance is the contra-variance. For instance, consider the following example:
<lang scala>def toName(e: Employee) = e.name val treeOfNames = t.map(toName)</lang>
This works, even though map is expecting a function from Manager into something, but toName is a function of Employee into String, and Employee is a supertype, not a subtype, of Manager. It works because functions have the following definition in Scala:
<lang scala>trait Function1[-T1, +R]</lang>
The minus sign indicates that this trait is contra-variant in T1, which happens to be the type of the argument of the function. In other words, it tell us that, Employee => String is a subtype of Manager => String, because Employee is a supertype of Manager. While the concept of contra-variance is not intuitive, it should be clear to anyone that toName can handle arguments of type Manager, but, were not for the contra-variance, it would not be usable with a Tree[Manager].
Let's add another method to Tree to see another concept:
<lang scala>case class Tree[+A](value: A, left: Option[Tree[A]], right: Option[Tree[A]]) {
def map[B](f: A => B): Tree[B] = Tree(f(value), left map (_.map(f)), right map (_.map(f))) def find[B >: A](what: B): Boolean = (value == what) || left.map(_.find(what)).getOrElse(false) || right.map(_.find(what)).getOrElse(false)
}</lang>
The type parameter of find is [B >: A]. That means the type is some B, as long as that B is a supertype of A. If I tried to declare what: A, Scala would not accept it. To understand why, let's consider the following code:
<lang scala>if (t2.find(new Employee("Dilbert")))
println("Call Catbert!")</lang>
Here we have find receiving an argument of type Employee, even though the tree it was defined on is of type Manager. The co-variance of Tree means a situation such as this is possible.
There is also an operator <:, with the opposite meaning of >:.
Finally, Scala also allows abstract types. Abtract types are similar to abstract methods: they have to be defined when a class is inherited. One simple example would be:
<lang scala>trait DFA {
type Element val map = new collection.mutable.HashMap[Element, DFA]()
}</lang>
A concrete class wishing to inherit from DFA would need to define Element. Abstract types aren't all that different from type parameters. Mainly, they ensure that the type will be selected in the definition site (the declaration of the concrete class), and not at the usage site (instantiation of the concrete class). The difference is mainly one of style, though.
Seed7
In Seed7 types like array and struct are not built-in, but are defined with parametric polymorphism. In the Seed7 documentation the terms "template" and "function with type parameters and type result" are used instead of "parametric polymorphism". E.g.: array is actually a function, which takes an element type as parameter and returns a type. To concentrate on the essentials, the example below defines the type container as array. Note that the map function has three parameters: aContainer, aVariable, and aFunc. When map is called aVariable is used also in the actual parameter of aFunc: map(container1, num, num + 1)
<lang seed7>$ include "seed7_05.s7i";
const func type: container (in type: elemType) is func
result var type: container is void; begin container := array elemType;
global
const func container: map (in container: aContainer,
inout elemType: aVariable, ref func elemType: aFunc) is func
result
var container: mapResult is container.value;
begin
for aVariable range aContainer do
mapResult &:= aFunc;
end for;
end func;
end global; end func;
const type: intContainer is container(integer); var intContainer: container1 is [] (1, 2, 4, 6, 10, 12, 16, 18, 22); var intContainer: container2 is 0 times 0;
const proc: main is func
local
var integer: num is 0;
begin
container2 := map(container1, num, num + 1);
for num range container2 do
write(num <& " ");
end for;
writeln;
end func;</lang>
Output:
2 3 5 7 11 13 17 19 23
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>
Swift
<lang swift>class Tree<T> {
var value: T?
var left: Tree<T>?
var right: Tree<T>?
func replaceAll(value: T?) {
self.value = value
left?.replaceAll(value)
right?.replaceAll(value)
}
}</lang>
Another version based on Algebraic Data Types:
<lang swift>enum Tree<T> {
case Empty
indirect case Node(T, Tree<T>, Tree<T>)
func map(f : T -> U) -> Tree {
switch(self) {
case .Empty : return .Empty
case let .Node(x, l, r): return .Node(f(x), l.map(f), r.map(f))
}
}
}</lang>
Ursala
Types are first class entities and functions to construct or operate on them may be defined routinely. A parameterized binary tree type can be defined using a syntax for anonymous recursion in type expressions as in this example, <lang Ursala>binary_tree_of "node-type" = "node-type"%hhhhWZAZ</lang> or by way of a recurrence solved using a fixed point combinator imported from a library as shown below. <lang Ursala>#import tag
- fix general_type_fixer 1
binary_tree_of "node-type" = ("node-type",(binary_tree_of "node-type")%Z)%drWZwlwAZ</lang>
(The %Z type operator constructs a "maybe" type, i.e., the free union of its operand type
with the null value. Others shown above are standard stack manipulation primitives, e.g. d (dup) and w (swap), used to build the type expression tree.) At the other extreme, one may construct an equivalent parameterized type in
point-free form.
<lang Ursala>binary_tree_of = %-hhhhWZAZ</lang>
A mapping combinator over this type can be defined with pattern matching like this
<lang Ursala>binary_tree_map "f" = ~&a^& ^A/"f"@an ~&amPfamPWB</lang>
or in point free form like this.
<lang Ursala>binary_tree_map = ~&a^&+ ^A\~&amPfamPWB+ @an</lang>
Here is a test program
defining a type of binary trees of strings, and a function that concatenates each node
with itself.
<lang Ursala>string_tree = binary_tree_of %s
x = 'foo': ('bar': (),'baz': ())
- cast string_tree
example = (binary_tree_map "s". "s"--"s") x</lang>
Type signatures are not necessarily associated with function declarations, but
have uses in the other contexts such as assertions and compiler directives
(e.g., #cast). Here is the output.
'foofoo': ('barbar': (),'bazbaz': ())
Visual Prolog
<lang prolog> domains
tree{Type} = branch(tree{Type} Left, tree{Type} Right); leaf(Type Value).
class predicates
treewalk : (tree{X},function{X,Y}) -> tree{Y} procedure (i,i).
clauses
treewalk(branch(Left,Right),Func) = branch(NewLeft,NewRight) :-
NewLeft = treewalk(Left,Func), NewRight = treewalk(Right,Func).
treewalk(leaf(Value),Func) = leaf(X) :-
X = Func(Value).
run():-
init(),
X = branch(leaf(2), branch(leaf(3),leaf(4))),
Y = treewalk(X,addone),
write(Y),
succeed().
</lang>
- Programming Tasks
- Basic language learning
- Type System
- Ada
- C
- C++
- C sharp
- Ceylon
- Clean
- Clojure/Omit
- Common Lisp
- D
- Dart
- E
- F Sharp
- Go
- Groovy
- Haskell
- Inform 7
- Icon
- Unicon
- J
- Java
- Mercury
- Nim
- Objective-C
- OCaml
- Oforth/Omit
- Perl 6
- PicoLisp
- Racket
- REXX
- Rust
- Scala
- Seed7
- Standard ML
- Swift
- Ursala
- Visual Prolog
- Axe/Omit
- C/Omit
- J/Omit
- JavaScript/Omit
- M4/Omit
- Maxima/Omit
- Oz/Omit
- Perl/Omit
- Python/Omit
- Ruby/Omit
- Tcl/Omit
- TI-83 BASIC/Omit
- TI-89 BASIC/Omit
- LaTeX/Omit
- Retro/Omit
- Zkl/Omit