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

 

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|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|Mercury}}==

 

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

 

map(_, empty) = empty.

 

=={{header|OCaml}}==

 

 

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

let rec map_tree f = function

| Empty -> Empty

 

 

{{out}}

 

=={{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.

<pre>

 

</pre>

 

=={{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|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|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}}