Parametric polymorphism: Difference between revisions

{{task|Basic language learning}}

[[Category:Type System]]

[[wp: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.

 

 

This language feature only applies to statically-typed languages.

 

=={{header|Ada}}==

type Element_Type is private;

package Container is

Right : Node_Access := null;

end record;

procedure Replace_All(The_Tree : in out Tree; New_Value : Element_Type) is

begin

end if;

end Replace_All;

 

=={{header|C}}==

#include <stdlib.h>

 

 

return 0;

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.

 

 

{

T value;

tree *left;

public:

void replace_all (T new_value);

 

For simplicity, we replace all values in the tree with a new value:

 

value = new_value;

 

 

 

 

=={{header|Ceylon}}==

 

shared BinaryTree<NewData> myMap<NewData>(NewData f(Data d)) =>

value tree2 = tree1.myMap((x) => x * 333.33);

tree2.myMap(print);

 

=={{header|Clean}}==

 

 

mapTree :: (a -> b) (Tree a) -> (Tree b)

mapTree f Empty = Empty

 

<blockquote><small>

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 <code>fmap</code> in an ''instance'' of the <code>Functor</code> ''type class'':

 

fmap f Empty = Empty

 

<code>fmap</code> can then be used exactly where <code>mapTree</code> can, but doing this also allows the use of <code>Tree</code>s 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:

 

 

If we have a tree of integers, i.e. <var>f</var> is <code>Tree</code> and <var>a</var> is <code>Integer</code>, then the type of <code>add1Everywhere</code> is <code>Tree Integer -> Tree Integer</code>.

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 <code>pair</code> is defined which accepts two (optional) type specifiers. An object is of type <code>(pair :car car-type :cdr cdr-type)</code> if an only if it is a cons whose car is of type <code>car-type</code> and whose cdr is of type <code>cdr-type</code>.

 

 

Example

 

=={{header|D}}==

T[N] data;

typeof(this) left, right;

//root.tmap(x => writefln("%(%.2f %)", x));

root.tmap((ref x) => writefln("%(%.2f %)", x));

{{out}}

<pre>1.00 1.00 1.00

 

=={{header|Dart}}==

T value;

print('second tree');

newRoot.forEach(print);

{{out}}

<pre>first tree

(Note: The guard definition is arguably messy boilerplate; future versions of E may provide a scheme where the <code>interface</code> 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.)

 

def Tree {

to get(Value) {

}

return tree

 

# value: <tree>

 

 

? t :Tree[int]

 

 

 

namespace RosettaCode

 

| Element(x) -> Element(f x)

| Tree(x,left,right) -> Tree((f x), left.Map(f), right.Map(f))

 

We can test this binary tree like so:

let t1 = Tree(2, Element(1), Tree(4,Element(3),Element(5)) )

let t2 = t1.Map(fun x -> x * 10)

 

=={{header|Fortran}}==

Fortran does not offer polymorphism by parameter type, which is to say, enables the same source code to be declared applicable for parameters of different types, so that a contained statement such as <code>X = A + B*C</code> would work for any combination of integer or floating-point or complex variables as actual parameters, since exactly that (source) code would be workable in every case. Further, there is no standardised pre-processor protocol whereby one could replicate such code to produce a separate subroutine or function specific to every combination.

 

 

INTERFACE FIND !Binary chop search, not indexed.

END FUNCTION FINDI4 !On success, THIS = NUMB(FINDI4); no fancy index here...

 

 

There would be a function (with a unique name) for each of the contemplated variations in parameter types, and when the compiler reached an invocation of FIND(...) it would select by matching amongst the combinations that had been defined in the routines named in the INTERFACE statement. The various actual functions could have different code, and in this case, only the <code>INTEGER*4 THIS,NUMB(1:*)</code> need be changed, say to <code>REAL*4 THIS,NUMB(1:*)</code> for FINDF4, which is why both variables are named in the one statement. However, for searching CHARACTER arrays, because the character comparison operations differ from those for numbers (and, no three-way IF-test either), additional changes are required. Thus, function FIND would appear to be a polymorphic function that accepts and returns a variety of types, but it is not, and indeed, there is actually no function called FIND anywhere in the compiled code.

 

 

 

=={{header|Go}}==

 

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

 

import "fmt"

visit(9)

}

Output:

<pre>

b-tree average: 5

</pre>

 

=={{header|Groovy}}==

{{trans|Java}} (more or less)

Solution:

T value

Tree<T> left

right?.replaceAll(value)

}

 

=={{header|Haskell}}==

 

 

mapTree :: (a -> b) -> Tree a -> Tree b

mapTree f Empty = Empty

 

<blockquote><small>

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 <code>fmap</code> in an ''instance'' of the <code>Functor</code> ''type class'':

 

fmap f Empty = Empty

 

<code>fmap</code> can then be used exactly where <code>mapTree</code> can, but doing this also allows the use of <code>Tree</code>s 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:

 

 

If we have a tree of integers, i.e. <var>f</var> is <code>Tree</code> and <var>a</var> is <code>Integer</code>, then the type of <code>add1Everywhere</code> is <code>Tree Integer -> Tree Integer</code>.

</small></blockquote>

 

=={{header|Inform 7}}==

Phrases (the equivalent of global functions) can be defined with type parameters:

 

To find (V - K) in (L - list of values of kind K):

find "needle" in {"parrot", "needle", "rutabaga"};

find 6 in {2, 3, 4};

 

Inform 7 does not allow user-defined parametric types. Some built-in types can be parameterized, though:

relation of texts to rooms

object based rulebook producing a number

number valued property

text valued table column

 

=={{header|J}}==

=={{header|Java}}==

Following the C++ example:

private T value;

private Tree<T> left;

public void replaceAll(T value){

this.value = value;

left.replaceAll(value);

right.replaceAll(value);

}

 

=={{header|Kotlin}}==

{{trans|C#}}

 

class BinaryTree<T>(var value: T) {

val b2 = b.map { it * 10.0 }

println(b2.showTopThree())

 

{{out}}

(50.0, 60.0, 70.0)

</pre>

 

=={{header|Mercury}}==

 

:- func map(func(A) = B, tree(A)) = tree(B).

 

map(_, empty) = empty.

 

=={{header|Nim}}==

value: T

 

=={{header|Objective-C}}==

{{trans|C++}}

{{works with|Xcode|7}}

T value;

Tree<T> *left;

[right replaceAll:v];

}

Note that the generic type variable is only used in the declaration, but not in the implementation.

 

=={{header|OCaml}}==

 

 

(** val map_tree : ('a -> 'b) -> 'a tree -> 'b tree *)

let rec map_tree f = function

| Empty -> Empty

 

{{omit from|Oforth|Oforth is nt statically-typed language}}

 

=={{header|Phix}}==

Of course many builtin routines are naturally generic, such as sort and print.<br>

Most programming languages would throw a hissy fit if you tried to sort (or print) a mixed collection of strings and integers, but not Phix:

{{out}}

<pre>

For comparison purposes (and because this entry looked a bit sparse without it) this is the D example from this page translated to Phix.<br>

Note that tmap has to be a function rather than a procedure with a reference parameter, but this still achieves

{{out}}

<pre>

=={{header|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):

(set Tree (Fun (car Tree)))

(and (cadr Tree) (mapTree @ Fun))

Test:

<pre style="height:20em;overflow:scroll">(balance 'MyTree (range 1 7)) # Create a tree of numbers

-> NIL</pre>

 

 

 

#lang typed/racket

 

(tree-map add1 (Node 5 (Node 3 #f #f) #f))

(Node 6 (Node 4 #f #f) #f))

 

=={{header|REXX}}==

This REXX programming example is modeled after the &nbsp; '''D''' &nbsp; example.

call newRoot 1.00, 3 /*new root, and also indicate 3 stems.*/

/* [↓] no need to label the stems. */

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

return

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

</pre>

 

=={{header|Rust}}==

value: T,

left: Option<Box<TreeNode<T>>>,

let new_root = root.my_map(&|x| *x as f64 * 333.333f64);

new_root.my_map(&|x| { println!("{}" , x) });

 

=={{header|Scala}}==

the example in question:

 

def map[B](f: A => B): Tree[B] =

Tree(f(value), left map (_.map(f)), right map (_.map(f)))

 

Note that the type parameter of the class <tt>Tree</tt>, <tt>[+A]</tt>. The

will be a subtype of <tt>Tree[Y]</tt> if <tt>X</tt> is a subtype of <tt>Y</tt>. For example:

 

class Manager(name: String) extends Employee(name)

 

val t = Tree(new Manager("PHB"), None, None)

 

The second assignment is legal because <tt>t</tt> is of type <tt>Tree[Manager]</tt>, and since

Another possible variance is the ''contra-variance''. For instance, consider the following example:

 

 

This works, even though <tt>map</tt> is expecting a function from <tt>Manager</tt> into something,

definition in Scala:

 

 

The minus sign indicates that this trait is ''contra-variant'' in <tt>T1</tt>, which happens to be

Let's add another method to <tt>Tree</tt> to see another concept:

 

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)

 

The type parameter of <tt>find</tt> is <tt>[B >: A]</tt>. That means the type is some <tt>B</tt>, as long

accept it. To understand why, let's consider the following code:

 

 

Here we have <tt>find</tt> receiving an argument of type <tt>Employee</tt>, even though the tree

to be defined when a class is inherited. One simple example would be:

 

type Element

val map = new collection.mutable.HashMap[Element, DFA]()

 

A concrete class wishing to inherit from <tt>DFA</tt> would need to define <tt>Element</tt>. Abstract

When ''map'' is called ''aVariable'' is used also in the actual parameter of ''aFunc'': map(container1, num, num + 1)

 

 

const func type: container (in type: elemType) is func

end for;

writeln;

 

Output:

 

=={{header|Standard ML}}==

 

(** val map_tree = fn : ('a -> 'b) -> 'a tree -> 'b tree *)

fun map_tree f Empty = Empty

 

=={{header|Swift}}==

{{trans|Java}}

var value: T?

var left: Tree<T>?

right?.replaceAll(value)

}

 

Another version based on Algebraic Data Types:

{{works with|Swift|2+}}

case Empty

indirect case Node(T, Tree<T>, Tree<T>)

}

}

 

=={{header|Ursala}}==

routinely. A parameterized binary tree type can be defined using a syntax for anonymous

recursion in type expressions as in this example,

or by way of a recurrence solved using a fixed point combinator imported from a library

as shown below.

 

#fix general_type_fixer 1

 

(The <code>%Z</code> 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. <code>d</code> (dup) and <code>w</code> (swap), used to build the type expression tree.) At the other extreme, one may construct an equivalent parameterized type in

point-free form.

A mapping combinator over this type can be defined with pattern matching like this

or in point free form like this.

Here is a test program

defining a type of binary trees of strings, and a function that concatenates each node

with itself.

 

x = 'foo': ('bar': (),'baz': ())

#cast string_tree

 

Type signatures are not necessarily associated with function declarations, but

have uses in the other contexts such as assertions and compiler directives

'foofoo': ('barbar': (),'bazbaz': ())

</pre>

 

=={{header|Visual Prolog}}==

domains

tree{Type} = branch(tree{Type} Left, tree{Type} Right); leaf(Type Value).

write(Y),

succeed().

 

 

 

{{omit from|Axe}}

{{omit from|C|no type variables in stdc}}

{{omit from|C|no type variables}}

{{omit from|J|not statically typed}}

{{omit from|JavaScript|not statically typed}}

{{omit from|LaTeX}}

{{omit from|Retro|typeless}}

{{omit from|zkl|typeless}}