Parametric polymorphism: Difference between revisions
PascalABC.NET |
|||
(45 intermediate revisions by 19 users not shown) | |||
Line 1: | Line 1: | ||
{{task|Basic language learning}} |
{{task|Basic language learning}} |
||
[[Category:Type System]] |
[[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. |
[[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. |
||
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. |
|||
;Task: |
|||
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. |
This language feature only applies to statically-typed languages. |
||
<br><br> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang="ada">generic |
||
type Element_Type is private; |
type Element_Type is private; |
||
package Container is |
package Container is |
||
Line 21: | Line 28: | ||
Right : Node_Access := null; |
Right : Node_Access := null; |
||
end record; |
end record; |
||
end Container;</ |
end Container;</syntaxhighlight> |
||
< |
<syntaxhighlight lang="ada">package body Container is |
||
procedure Replace_All(The_Tree : in out Tree; New_Value : Element_Type) is |
procedure Replace_All(The_Tree : in out Tree; New_Value : Element_Type) is |
||
begin |
begin |
||
Line 33: | Line 40: | ||
end if; |
end if; |
||
end Replace_All; |
end Replace_All; |
||
end Container;</ |
end Container;</syntaxhighlight> |
||
=={{header|C}}== |
=={{header|C}}== |
||
If the goal is to separate algorithms from types at compile |
If the goal is to separate algorithms from types at compile time, C may do it by macros. Here's sample code implementing binary tree with node creation and insertion:<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 82: | Line 89: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
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. |
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. |
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. |
||
=={{header|C |
=={{header|C sharp|C#}}== |
||
<syntaxhighlight lang="csharp">using System; |
|||
class BinaryTree<T> |
|||
<lang cpp>template<class T> |
|||
class tree |
|||
{ |
{ |
||
public T value; |
|||
public BinaryTree<T> left; |
|||
public BinaryTree<T> right; |
|||
public BinaryTree(T value) |
|||
{ |
|||
this.value = value; |
|||
} |
|||
public BinaryTree<U> Map<U>(Func<T, U> f) |
|||
{ |
|||
BinaryTree<U> tree = new BinaryTree<U>(f(this.value)); |
|||
if (this.left != null) |
|||
{ |
|||
tree.left = this.left.Map(f); |
|||
} |
|||
if (this.right != null) |
|||
{ |
|||
tree.right = this.right.Map(f); |
|||
} |
|||
return tree; |
|||
} |
|||
}</syntaxhighlight> |
|||
Creating a tree of integers and using Map to generate a tree of doubles with every node half the value of the first: |
|||
<syntaxhighlight lang="csharp">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 * 0.5); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{anchor|C# modern version}}A version using more modern language constructs: |
|||
<syntaxhighlight lang="csharp">using System; |
|||
class BinaryTree<T> |
|||
{ |
|||
public BinaryTree<T> Left { get; } |
|||
public BinaryTree<T> Right { get; } |
|||
public T Value { get; } |
|||
public BinaryTree(T value, BinaryTree<T> left = null, BinaryTree<T> right = null) |
|||
{ |
|||
this.Value = value; |
|||
this.Left = left; |
|||
this.Right = right; |
|||
} |
|||
public BinaryTree<U> Map<U>(Func<T, U> f) |
|||
{ |
|||
return new BinaryTree<U>(f(this.Value), this.Left?.Map(f), this.Right?.Map(f)); |
|||
} |
|||
public override string ToString() |
|||
{ |
|||
var sb = new System.Text.StringBuilder(); |
|||
this.ToString(sb, 0); |
|||
return sb.ToString(); |
|||
} |
|||
private void ToString(System.Text.StringBuilder sb, int depth) |
|||
{ |
|||
sb.Append(new string('\t', depth)); |
|||
sb.AppendLine(this.Value?.ToString()); |
|||
this.Left?.ToString(sb, depth + 1); |
|||
this.Right?.ToString(sb, depth + 1); |
|||
} |
|||
} |
|||
static class Program |
|||
{ |
|||
static void Main() |
|||
{ |
|||
var b = new BinaryTree<int>(6, new BinaryTree<int>(5), new BinaryTree<int>(7)); |
|||
BinaryTree<double> b2 = b.Map(x => x * 0.5); |
|||
Console.WriteLine(b); |
|||
Console.WriteLine(b2); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>6 |
|||
5 |
|||
7 |
|||
3 |
|||
2.5 |
|||
3.5</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="cpp">template<typename T> |
|||
class tree { |
|||
T value; |
T value; |
||
tree *left; |
tree *left; |
||
Line 97: | Line 206: | ||
public: |
public: |
||
void replace_all (T new_value); |
void replace_all (T new_value); |
||
};</ |
};</syntaxhighlight> |
||
For simplicity, we replace all values in the tree with a new value: |
For simplicity, we replace all values in the tree with a new value: |
||
< |
<syntaxhighlight lang="cpp">template<class T> |
||
void tree<T>::replace_all |
void tree<T>::replace_all(T new_value) { |
||
{ |
|||
value = new_value; |
value = new_value; |
||
if (left != |
if (left != nullptr) |
||
left->replace_all |
left->replace_all(new_value); |
||
if (right != |
if (right != nullptr) |
||
right->replace_all |
right->replace_all(new_value); |
||
}</ |
}</syntaxhighlight> |
||
=={{header| |
=={{header|C3}}== |
||
<syntaxhighlight lang="c3">module tree(<Type>); |
|||
<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<U> Map<U>(Func<T,U> f) { |
|||
BinaryTree<U> Tree = new BinaryTree<U>(f(this.value)); |
|||
if (left != null) { |
|||
Tree.left = left.Map(f); |
|||
} |
|||
if (right != null) { |
|||
Tree.right = right.Map(f); |
|||
} |
|||
return Tree; |
|||
} |
|||
} |
|||
}</lang> |
|||
struct Tree |
|||
Sample that creates a tree to hold int values: |
|||
{ |
|||
Type value; |
|||
Tree* left; |
|||
Tree* right; |
|||
} |
|||
fn void Tree.replace_all(&self, Type new_value) |
|||
<lang csharp>namespace RosettaCode { |
|||
{ |
|||
class Program { |
|||
self.value = new_value; |
|||
static void Main(string[] args) { |
|||
if (self.left) self.left.replace_all(new_value); |
|||
BinaryTree<int> b = new BinaryTree<int>(6); |
|||
if (self.right) self.right.replace_all(new_value); |
|||
b.left = new BinaryTree<int>(5); |
|||
} |
|||
b.right = new BinaryTree<int>(7); |
|||
</syntaxhighlight> |
|||
BinaryTree<double> b2 = b.Map(x => x * 10.0); |
|||
} |
|||
Usage: |
|||
} |
|||
<syntaxhighlight lang="c3">import tree; |
|||
}</lang> |
|||
fn void test() |
|||
{ |
|||
Tree(<int>) inttree; |
|||
inttree.replace_all(3); |
|||
}</syntaxhighlight> |
|||
=={{header|Ceylon}}== |
=={{header|Ceylon}}== |
||
< |
<syntaxhighlight lang="ceylon">class BinaryTree<Data>(shared Data data, shared BinaryTree<Data>? left = null, shared BinaryTree<Data>? right = null) { |
||
shared BinaryTree<NewData> myMap<NewData>(NewData f(Data d)) => |
shared BinaryTree<NewData> myMap<NewData>(NewData f(Data d)) => |
||
Line 180: | Line 278: | ||
value tree2 = tree1.myMap((x) => x * 333.33); |
value tree2 = tree1.myMap((x) => x * 333.33); |
||
tree2.myMap(print); |
tree2.myMap(print); |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Clean}}== |
=={{header|Clean}}== |
||
< |
<syntaxhighlight lang="clean">::Tree a = Empty | Node a (Tree a) (Tree a) |
||
mapTree :: (a -> b) (Tree a) -> (Tree b) |
mapTree :: (a -> b) (Tree a) -> (Tree b) |
||
mapTree f Empty = Empty |
mapTree f Empty = Empty |
||
mapTree f (Node x l r) = Node (f x) (mapTree f l) (mapTree f r)</ |
mapTree f (Node x l r) = Node (f x) (mapTree f l) (mapTree f r)</syntaxhighlight> |
||
<blockquote><small> |
<blockquote><small> |
||
Line 195: | Line 293: | ||
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'': |
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'': |
||
< |
<syntaxhighlight lang="clean">instance Functor Tree where |
||
fmap f Empty = Empty |
fmap f Empty = Empty |
||
fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)</ |
fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)</syntaxhighlight> |
||
<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: |
<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: |
||
< |
<syntaxhighlight lang="clean">add1Everywhere :: (f a) -> (f a) | Functor f & Num a |
||
add1Everywhere nums = fmap (\x = x + 1) nums</ |
add1Everywhere nums = fmap (\x = x + 1) nums</syntaxhighlight> |
||
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>. |
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>. |
||
Line 208: | Line 306: | ||
{{omit from|Clojure}} |
{{omit from|Clojure}} |
||
=={{header|COBOL}}== |
|||
<syntaxhighlight lang="cobolfree"> >>SOURCE FORMAT IS FREE |
|||
IDENTIFICATION DIVISION. |
|||
CLASS-ID. Tree INHERITS FROM Base USING X. |
|||
DATE-WRITTEN. 20240702. |
|||
ENVIRONMENT DIVISION. |
|||
CONFIGURATION SECTION. |
|||
OBJECT-COMPUTER. |
|||
MEMORY SIZE IS 1073741824 CHARACTERS. |
|||
REPOSITORY. |
|||
CLASS Base. |
|||
CLASS X. |
|||
IDENTIFICATION DIVISION. |
|||
OBJECT. |
|||
DATA DIVISION. |
|||
WORKING-STORAGE SECTION. |
|||
77 ws-value USAGE IS OBJECT REFERENCE X ONLY. |
|||
77 ws-left USAGE IS OBJECT REFERENCE Tree ONLY. |
|||
77 ws-right USAGE IS OBJECT REFERENCE Tree ONLY. |
|||
PROCEDURE DIVISION. |
|||
IDENTIFICATION DIVISION. |
|||
METHOD-ID. replace_all. |
|||
DATA DIVISION. |
|||
LINKAGE SECTION. |
|||
77 new_value USAGE IS OBJECT REFERENCE X ONLY. |
|||
PROCEDURE DIVISION USING BY REFERENCE new_value. |
|||
MOVE new_value TO ws-value. |
|||
IF ws-left IS NOT EQUAL TO NULL THEN |
|||
INVOKE ws-left "replace_all" USING BY REFERENCE new_value. |
|||
IF ws-right IS NOT EQUAL TO NULL THEN |
|||
INVOKE ws-right "replace_all" USING BY REFERENCE new_value. |
|||
GOBACK. |
|||
END METHOD replace_all. |
|||
END OBJECT. |
|||
END CLASS Tree.</syntaxhighlight> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
Line 213: | Line 348: | ||
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>. |
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>. |
||
< |
<syntaxhighlight lang="lisp">(deftype pair (&key (car 't) (cdr 't)) |
||
`(cons ,car ,cdr))</ |
`(cons ,car ,cdr))</syntaxhighlight> |
||
Example |
Example |
||
Line 225: | Line 360: | ||
=={{header|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang="d">class ArrayTree(T, uint N) { |
||
T[N] data; |
T[N] data; |
||
typeof(this) left, right; |
typeof(this) left, right; |
||
Line 270: | Line 405: | ||
//root.tmap(x => writefln("%(%.2f %)", x)); |
//root.tmap(x => writefln("%(%.2f %)", x)); |
||
root.tmap((ref x) => writefln("%(%.2f %)", x)); |
root.tmap((ref x) => writefln("%(%.2f %)", x)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1.00 1.00 1.00 |
<pre>1.00 1.00 1.00 |
||
Line 289: | Line 424: | ||
=={{header|Dart}}== |
=={{header|Dart}}== |
||
< |
<syntaxhighlight lang="dart">class TreeNode<T> { |
||
T value; |
T value; |
||
Line 330: | Line 465: | ||
print('second tree'); |
print('second tree'); |
||
newRoot.forEach(print); |
newRoot.forEach(print); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>first tree |
<pre>first tree |
||
Line 351: | Line 486: | ||
(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.) |
(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.) |
||
< |
<syntaxhighlight lang="e">interface TreeAny guards TreeStamp {} |
||
def Tree { |
def Tree { |
||
to get(Value) { |
to get(Value) { |
||
Line 381: | Line 516: | ||
} |
} |
||
return tree |
return tree |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="e">? def t := makeTree(int, 0, null, null) |
||
# value: <tree> |
# value: <tree> |
||
Line 393: | Line 528: | ||
? t :Tree[int] |
? t :Tree[int] |
||
# value: <tree></ |
# value: <tree></syntaxhighlight> |
||
=={{header|FreeBASIC}}== |
|||
{{trans|Visual Basic .NET}} |
|||
FreeBASIC does not support object-oriented programming, so we will use a more procedural approach. |
|||
<syntaxhighlight lang="vbnet">Type BinaryTree |
|||
valor As Integer |
|||
izda As BinaryTree Ptr |
|||
dcha As BinaryTree Ptr |
|||
End Type |
|||
Sub PrintTree(t As BinaryTree Ptr, depth As Integer) |
|||
=={{header|F_Sharp|F#}}== |
|||
If t = 0 Then Exit Sub |
|||
Print String(depth, Chr(9)); t->valor |
|||
PrintTree(t->izda, depth + 1) |
|||
PrintTree(t->dcha, depth + 1) |
|||
End Sub |
|||
Dim As BinaryTree b = Type(6) |
|||
<lang fsharp> |
|||
Dim As BinaryTree bLeft = Type(5) |
|||
Dim As BinaryTree bRight = Type(7) |
|||
b.izda = @bLeft |
|||
b.dcha = @bRight |
|||
PrintTree(@b, 0)</syntaxhighlight> |
|||
=={{header|F_Sharp|F#}}== |
|||
<syntaxhighlight lang="fsharp"> |
|||
namespace RosettaCode |
namespace RosettaCode |
||
Line 408: | Line 565: | ||
| Element(x) -> Element(f x) |
| Element(x) -> Element(f x) |
||
| Tree(x,left,right) -> Tree((f x), left.Map(f), right.Map(f)) |
| Tree(x,left,right) -> Tree((f x), left.Map(f), right.Map(f)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
We can test this binary tree like so: |
We can test this binary tree like so: |
||
< |
<syntaxhighlight lang="fsharp"> |
||
let t1 = Tree(2, Element(1), Tree(4,Element(3),Element(5)) ) |
let t1 = Tree(2, Element(1), Tree(4,Element(3),Element(5)) ) |
||
let t2 = t1.Map(fun x -> x * 10) |
let t2 = t1.Map(fun x -> x * 10) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Fortran}}== |
=={{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 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. |
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. |
||
However, with F90 came the MODULE protocol with facilities suitable for defining "generic" subroutines or functions, or so it appears: < |
However, with F90 came the MODULE protocol with facilities suitable for defining "generic" subroutines or functions, or so it appears: <syntaxhighlight lang="fortran"> MODULE SORTSEARCH !Genuflect towards Prof. D. Knuth. |
||
INTERFACE FIND !Binary chop search, not indexed. |
INTERFACE FIND !Binary chop search, not indexed. |
||
Line 454: | Line 610: | ||
END FUNCTION FINDI4 !On success, THIS = NUMB(FINDI4); no fancy index here... |
END FUNCTION FINDI4 !On success, THIS = NUMB(FINDI4); no fancy index here... |
||
END MODULE SORTSEARCH </ |
END MODULE SORTSEARCH </syntaxhighlight> |
||
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, |
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. |
||
That said, some systems had polymorphic variables, such as the B6700 whereby integers were represented as floating-point numbers and so exactly the same function could be presented with an integer or a floating-point variable (provided the compiler didn't check for parameter type matching - but this was routine) and it would work - so long as no divisions were involved since addition, subtraction, and multiplication are the same for both, but integer division discards any remainders. More recent computers following the Intel 8087 floating-point processor and similar add novel states to the scheme for floating-point arithmetic: not just zero and "gradual underflow" but "Infinity" and "Not a Number", which last violates even more of the axia of mathematics in that ''NaN'' does not equal ''NaN''. In turn, this forces a modicum of polymorphism into the language so as to contend with the additional features, such as the special function IsNaN(x). |
|||
More generally, using the same code for different types of variable can be problematical. A scheme that works in single precision may not work in double precision (or ''vice-versa'') or may not give corresponding levels of accuracy, or not converge at all, ''etc.'' While F90 also standardised special functions that give information about the precision of variables and the like, and in principle, a method could be coded that, guided by such information, would work for different precisions, this sort of scheme is beset by all manner of difficulties in problems more complex than the simple examples in text books. Polymorphism just exacerbates the difficulties, but sometimes it is not so troublesome, as in [[Pathological_floating_point_problems#The_Chaotic_Bank_Society]] whereby the special EPSILON(x) function that reports on the precision of a nominated variable of type ''x'' is used to determine the point beyond which further calculation (in that precision, for that formula) will make no difference. |
|||
More generally, using the same code for different types of variable can be problematical. A scheme that works in single precision may not work in double precision (or ''vice-versa'') or may not give corresponding levels of accuracy, or not converge at all, ''etc.'' While F90 also standardised special functions that give information about the precision of variables and the like, and in principle, a method could be coded that, guided by such information, would work for different precisions, this sort of scheme is beset by all manner of difficulties in problems more complex than the simple examples of text books. |
|||
Polymorphism just exacerbates the difficulties, thus, on page 219 of ''16-Bit Modern Microcomputers'' by G. M. Corsline appears the remark "At least some of the generalized numerical solutions to common mathematical procedures have coding that is so involved and tricky in order to take care of all possible roundoff contingencies that they have been termed 'pornographic algorithms'.". And "Mathematical software is easy for the uninitiated to write but notoriously hard for the expert. This paradox exists because the beginner is satisfied if his code usually works in his own machine while the expert attempts, against overwhelming obstacles, to produce programs that always work on a large number of computers. The problem is that while standard formulas of mathematics are fairly easy to translate into FORTRAN they often are subject to instabilities due to roundoff error." - quoting John Palmer, 1980, Intel Corporation. |
|||
But sometimes it is not so troublesome, as in [[Pathological_floating_point_problems#The_Chaotic_Bank_Society]] whereby the special EPSILON(x) function that reports on the precision of a nominated variable of type ''x'' is used to determine the point beyond which further calculation (in that precision, for that formula) will make no difference. |
|||
Having flexible facilities available my lead one astray. Consider the following data aggregate, as became available with F90: <syntaxhighlight lang="fortran"> TYPE STUFF |
|||
INTEGER CODE !A key number. |
|||
CHARACTER*6 NAME !Associated data. |
|||
INTEGER THIS !etc. |
|||
END TYPE STUFF |
|||
TYPE(STUFF) TABLE(600) !An array of such entries. </syntaxhighlight> |
|||
Suppose the array was in sorted order by each entry's value of CODE so that TABLE(1).CODE <= TABLE(2).CODE, etc. and one wished to find the index of an entry with a specific value, ''x'', of CODE. It is pleasing to be able to write <code>FIND(x,TABLE.CODE,N)</code> and have it accepted by the compiler. Rather less pleasing is that it runs very slowly. |
|||
This is because consecutive elements in an array are expected to occupy consecutive locations in storage, but the CODE elements do not, being separated by the other elements of the aggregate. So, the compiler generates code to copy the required elements to a work area, presents that as the actual parameter, and copies from the work area back on return from the function, thereby vitiating the speed advantages of the binary search. This is why the <code>INTENT(IN)</code> might help in such situations, as will writing <code>FIND(x,TABLE(1:N).CODE,N)</code> should N be often less than the full size of the table. But really, in-line code for each such usage is the only answer, despite the lack of a pre-processor to generate it. |
|||
Other options are to remain with the older-style of Fortran, using separately-defined arrays having a naming convention such as TABLECODE(600), TABLENAME(600), ''etc''. thus not gaining the unity of declaring a TYPE, or, declaring the size within the type as in <code>INTEGER CODE(600)</code> except that this means that the size is a part of the type and different-sized tables would require different types, or, perhaps the compiler will handle this problem by passing a "stride" value for every array dimension so that subroutines and functions can index such parameters properly - at the cost of yet more overhead for parameter passing, and more complex indexing calculations. |
|||
In short, the available polymorphism whereby a parameter can be a normal array, or, an array-like "selection" of a component from an array of compound entities enables appealing syntax, but disasterous performance. |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
Line 467: | Line 643: | ||
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.) |
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.) |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 519: | Line 695: | ||
visit(9) |
visit(9) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 525: | Line 701: | ||
b-tree average: 5 |
b-tree average: 5 |
||
</pre> |
</pre> |
||
Alternatively, if generics are introduced into Go based on the current design, this is how the C++ example might look if translated to Go: |
|||
<syntaxhighlight lang="go">package rosettacode |
|||
type Tree(type T) struct { |
|||
val T |
|||
left *Tree(T) |
|||
right *Tree(T) |
|||
} |
|||
func (t *Tree(T)) ReplaceAll(rep T) { |
|||
t.val = rep |
|||
if t.left != nil { t.left.ReplaceAll(rep) } |
|||
if t.right != nil { t.right.ReplaceAll(rep) } |
|||
}</syntaxhighlight> |
|||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
{{trans|Java}} (more or less) |
{{trans|Java}} (more or less) |
||
Solution: |
Solution: |
||
< |
<syntaxhighlight lang="groovy">class Tree<T> { |
||
T value |
T value |
||
Tree<T> left |
Tree<T> left |
||
Line 545: | Line 736: | ||
right?.replaceAll(value) |
right?.replaceAll(value) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">data Tree a = Empty | Node a (Tree a) (Tree a) |
||
mapTree :: (a -> b) -> Tree a -> Tree b |
mapTree :: (a -> b) -> Tree a -> Tree b |
||
mapTree f Empty = Empty |
mapTree f Empty = Empty |
||
mapTree f (Node x l r) = Node (f x) (mapTree f l) (mapTree f r)</ |
mapTree f (Node x l r) = Node (f x) (mapTree f l) (mapTree f r)</syntaxhighlight> |
||
<blockquote><small> |
<blockquote><small> |
||
Line 560: | Line 751: | ||
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'': |
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'': |
||
< |
<syntaxhighlight lang="haskell">instance Functor Tree where |
||
fmap f Empty = Empty |
fmap f Empty = Empty |
||
fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)</ |
fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)</syntaxhighlight> |
||
<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: |
<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: |
||
< |
<syntaxhighlight lang="haskell">add1Everywhere :: (Functor f, Num a) => f a -> f a |
||
add1Everywhere nums = fmap (\x -> x + 1) nums</ |
add1Everywhere nums = fmap (\x -> x + 1) nums</syntaxhighlight> |
||
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>. |
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> |
</small></blockquote> |
||
=={{header|Icon}} and {{header|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 <i>n</i>-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. |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
=={{header|Inform 7}}== |
=={{header|Inform 7}}== |
||
Phrases (the equivalent of global functions) can be defined with type parameters: |
Phrases (the equivalent of global functions) can be defined with type parameters: |
||
< |
<syntaxhighlight lang="inform7">Polymorphism is a room. |
||
To find (V - K) in (L - list of values of kind K): |
To find (V - K) in (L - list of values of kind K): |
||
Line 586: | Line 795: | ||
find "needle" in {"parrot", "needle", "rutabaga"}; |
find "needle" in {"parrot", "needle", "rutabaga"}; |
||
find 6 in {2, 3, 4}; |
find 6 in {2, 3, 4}; |
||
end the story.</ |
end the story.</syntaxhighlight> |
||
Inform 7 does not allow user-defined parametric types. Some built-in types can be parameterized, though: |
Inform 7 does not allow user-defined parametric types. Some built-in types can be parameterized, though: |
||
< |
<syntaxhighlight lang="inform7">list of numbers |
||
relation of texts to rooms |
relation of texts to rooms |
||
object based rulebook producing a number |
object based rulebook producing a number |
||
Line 596: | Line 805: | ||
number valued property |
number valued property |
||
text valued table column |
text valued table column |
||
phrase (text, text) -> number</ |
phrase (text, text) -> number</syntaxhighlight> |
||
=={{header|Icon}} and {{header|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 <i>n</i>-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> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Line 626: | Line 817: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
Following the C++ example: |
Following the C++ example: |
||
< |
<syntaxhighlight lang="java">public class Tree<T>{ |
||
private T value; |
private T value; |
||
private Tree<T> left; |
private Tree<T> left; |
||
Line 633: | Line 824: | ||
public void replaceAll(T value){ |
public void replaceAll(T value){ |
||
this.value = value; |
this.value = value; |
||
if(left != null) |
if (left != null) |
||
left.replaceAll(value); |
left.replaceAll(value); |
||
if(right != null) |
if (right != null) |
||
right.replaceAll(value); |
right.replaceAll(value); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Julia}}== |
|||
{{works with|Julia|1.6}} |
|||
<syntaxhighlight lang="julia">module BinaryTrees |
|||
mutable struct BinaryTree{V} |
|||
v::V |
|||
l::Union{BinaryTree{V}, Nothing} |
|||
r::Union{BinaryTree{V}, Nothing} |
|||
end |
|||
BinaryTree(v) = BinaryTree(v, nothing, nothing) |
|||
map(f, bt::BinaryTree) = BinaryTree(f(bt.v), map(f, bt.l), map(f, bt.r)) |
|||
map(f, bt::Nothing) = nothing |
|||
let inttree = BinaryTree( |
|||
0, |
|||
BinaryTree( |
|||
1, |
|||
BinaryTree(3), |
|||
BinaryTree(5), |
|||
), |
|||
BinaryTree( |
|||
2, |
|||
BinaryTree(4), |
|||
nothing, |
|||
), |
|||
) |
|||
map(x -> 2x^2, inttree) |
|||
end |
|||
let strtree = BinaryTree( |
|||
"hello", |
|||
BinaryTree( |
|||
"world!", |
|||
BinaryTree("Julia"), |
|||
nothing, |
|||
), |
|||
BinaryTree( |
|||
"foo", |
|||
BinaryTree("bar"), |
|||
BinaryTree("baz"), |
|||
), |
|||
) |
|||
map(uppercase, strtree) |
|||
end |
|||
end</syntaxhighlight> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
< |
<syntaxhighlight lang="scala">// version 1.0.6 |
||
class BinaryTree<T>(var value: T) { |
class BinaryTree<T>(var value: T) { |
||
Line 665: | Line 906: | ||
val b2 = b.map { it * 10.0 } |
val b2 = b.map { it * 10.0 } |
||
println(b2.showTopThree()) |
println(b2.showTopThree()) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 672: | Line 913: | ||
(50.0, 60.0, 70.0) |
(50.0, 60.0, 70.0) |
||
</pre> |
</pre> |
||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
The Wolfram language is naturally polymorphic. Function can (generally) accept any type. Here an example to join two lists of with different types and an example of squaring an input: |
|||
<syntaxhighlight lang="mathematica">f[a_] := Join[a, a] |
|||
f[{1, 2, 3}] |
|||
f[{"1", "2", "3"}] |
|||
f[{1.1, 2.1, 3.1}] |
|||
f[G[1, "a", Pi]] |
|||
g[x_] := x^2 |
|||
g[2] |
|||
g[3.5] |
|||
g[Pi] |
|||
g["a"]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{1,2,3,1,2,3} |
|||
{1,2,3,1,2,3} |
|||
{1.1,2.1,3.1,1.1,2.1,3.1} |
|||
G[1,a,\[Pi],1,a,\[Pi]] |
|||
4 |
|||
12.25 |
|||
\[Pi]^2 |
|||
(a)^2</pre> |
|||
=={{header|Mercury}}== |
=={{header|Mercury}}== |
||
< |
<syntaxhighlight lang="mercury">:- type tree(A) ---> empty ; node(A, tree(A), tree(A)). |
||
:- func map(func(A) = B, tree(A)) = tree(B). |
:- func map(func(A) = B, tree(A)) = tree(B). |
||
map(_, empty) = empty. |
map(_, empty) = empty. |
||
map(F, node(A, Left, Right)) = node(F(A), map(F, Left), map(F, Right)).</ |
map(F, node(A, Left, Right)) = node(F(A), map(F, Left), map(F, Right)).</syntaxhighlight> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
<syntaxhighlight lang="nim">import strutils, sugar |
|||
<lang nim>type Tree[T] = ref object |
|||
type Tree[T] = ref object |
|||
value: T |
value: T |
||
left, right: Tree[T] |
left, right: Tree[T] |
||
proc newTree[T](value = default(T)): Tree[T] = |
|||
## Create a tree with a single node with the given value. |
|||
Tree[T](value: value) |
|||
proc map[T, U](tree: Tree[T]; f: (T) -> U): Tree[U] = |
|||
## Apply function "f" to each element of a tree, building |
|||
## another tree. |
|||
result = newTree[U](f(tree.value)) |
|||
if not tree.left.isNil: |
|||
result.left = tree.left.map(f) |
|||
if not tree.right.isNil: |
|||
result.right = tree.right.map(f) |
|||
proc print(tree: Tree; indent = 0) = |
|||
## Print a tree. |
|||
let start = repeat(' ', indent) |
|||
echo start, "value: ", tree.value |
|||
if tree.left.isNil: |
|||
echo start, " nil" |
|||
else: |
|||
print(tree.left, indent + 2) |
|||
if tree.right.isNil: |
|||
echo start, " nil" |
|||
else: |
|||
print(tree.right, indent + 2) |
|||
when isMainModule: |
|||
echo "Initial tree:" |
|||
var tree = newTree[int](5) |
|||
tree.left = newTree[int](2) |
|||
tree.right = newTree[int](7) |
|||
print(tree) |
|||
echo "" |
|||
echo "Tree created by applying a function to each node:" |
|||
let tree1 = tree.map((x) => 1 / x) |
|||
print(tree1)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Initial tree: |
|||
value: 5 |
|||
value: 2 |
|||
nil |
|||
nil |
|||
value: 7 |
|||
nil |
|||
nil |
|||
Tree created by applying a function to each node: |
|||
value: 0.2 |
|||
value: 0.5 |
|||
nil |
|||
nil |
|||
value: 0.1428571428571428 |
|||
nil |
|||
nil</pre> |
|||
=={{header|Objective-C}}== |
=={{header|Objective-C}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
{{works with|Xcode|7}} |
{{works with|Xcode|7}} |
||
< |
<syntaxhighlight lang="objc">@interface Tree<T> : NSObject { |
||
T value; |
T value; |
||
Tree<T> *left; |
Tree<T> *left; |
||
Line 704: | Line 1,031: | ||
[right replaceAll:v]; |
[right replaceAll:v]; |
||
} |
} |
||
@end</ |
@end</syntaxhighlight> |
||
Note that the generic type variable is only used in the declaration, but not in the implementation. |
Note that the generic type variable is only used in the declaration, but not in the implementation. |
||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
< |
<syntaxhighlight lang="ocaml">type 'a tree = Empty | Node of 'a * 'a tree * 'a tree |
||
(** val map_tree : ('a -> 'b) -> 'a tree -> 'b tree *) |
(** val map_tree : ('a -> 'b) -> 'a tree -> 'b tree *) |
||
let rec map_tree f = function |
let rec map_tree f = function |
||
| Empty -> Empty |
| Empty -> Empty |
||
| Node (x,l,r) -> Node (f x, map_tree f l, map_tree f r)</ |
| Node (x,l,r) -> Node (f x, map_tree f l, map_tree f r)</syntaxhighlight> |
||
{{omit from|Oforth|Oforth is nt statically-typed language}} |
{{omit from|Oforth|Oforth is nt statically-typed language}} |
||
=={{header| |
=={{header|PascalABC.NET}}== |
||
<syntaxhighlight lang="delphi"> |
|||
<lang perl6>role BinaryTree[::T] { |
|||
type Node<T> = auto class |
|||
has T $.value; |
|||
data: T; |
|||
has BinaryTree[T] $.left; |
|||
left,right: Node<T>; |
|||
has BinaryTree[T] $.right; |
|||
end; |
|||
function CreateTree(n: integer): Node<integer>; |
|||
method replace-all(T $value) { |
|||
begin |
|||
$!value = $value; |
|||
if n = 0 then |
|||
$!left.replace-all($value) if $!left.defined; |
|||
Result := nil |
|||
$!right.replace-all($value) if $!right.defined; |
|||
else |
|||
Result := new Node<integer>( |
|||
} |
|||
Random(100), |
|||
CreateTree((n-1) div 2), |
|||
CreateTree(n-1 - (n-1) div 2) |
|||
); |
|||
end; |
|||
procedure InfixTraverse<T>(root: Node<T>; act: T -> ()); |
|||
class IntTree does BinaryTree[Int] { } |
|||
begin |
|||
if root = nil then |
|||
exit; |
|||
InfixTraverse(root.left,act); |
|||
act(root.data); |
|||
InfixTraverse(root.right,act); |
|||
end; |
|||
begin |
|||
my IntTree $it .= new(value => 1, |
|||
var tree := CreateTree(10); |
|||
left => IntTree.new(value => 2), |
|||
Println(tree); |
|||
right => IntTree.new(value => 3)); |
|||
InfixTraverse(tree, x -> Print(x)); |
|||
end. |
|||
$it.replace-all(42); |
|||
</syntaxhighlight> |
|||
say $it.perl;</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
|||
<pre>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]))</pre> |
|||
(58,(52,(3,nil,nil),(35,nil,(25,nil,nil))),(29,(3,nil,(50,nil,nil)),(2,nil,(86,nil,nil)))) |
|||
3 52 35 25 58 3 50 29 2 86 |
|||
</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 757: | Line 1,100: | ||
Of course many builtin routines are naturally generic, such as sort and print.<br> |
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: |
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: |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>?sort(shuffle({5,"oranges",6,"apples",7}))</lang> |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">({</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"oranges"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"apples"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">}))</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 764: | Line 1,109: | ||
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> |
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 |
Note that tmap has to be a function rather than a procedure with a reference parameter, but this still achieves |
||
pass-by-reference/in-situ updates, mainly because root is a local rather than global/static, and is the target |
pass-by-reference/in-situ updates, mainly because root is a local rather than global/static, and is the target of |
||
(aka assigned to/overwritten on return from) the top-level tmap() call, and yet also manages the C#/Dart/Kotlin |
|||
thing (by which I am referring to those specific examples on this page) of creating a whole new tree, simply |
|||
because lhs assignee!=rhs reference (aka root2!=root) in "root2 = tmap(root,rid)", not that such a "deep clone" |
|||
would (barring a few dirty low-level tricks) behave any differently to "root2=root", which is "a straightforward shared reference |
|||
<lang Phix>enum data, left, right |
|||
with cow semantics". Aside: this example lost a little bit of it's charm when the deep_copy() had to go in to make it pwa/p2js compatible, which has somewhat negated the previous sentence, but that was happening implicitly anyway, and the depths of 1 (ie ",1" on the deep_copy()) retain similar efficiency. |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
function tmap(sequence tree, integer rid) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
tree[data] = call_func(rid,{tree[data]}) |
|||
<span style="color: #008080;">enum</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">left</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">right</span> |
|||
if tree[left]!=null then tree[left] = tmap(tree[left],rid) end if |
|||
if tree[right]!=null then tree[right] = tmap(tree[right],rid) end if |
|||
return tree |
|||
end function |
|||
function newnode(object v) |
|||
return {v,null,null} |
|||
end function |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">tmap</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">rid</span><span style="color: #0000FF;">)</span> |
|||
function add10(atom x) return x+10 end function |
|||
<span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">data</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rid</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">data</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">left</span><span style="color: #0000FF;">]!=</span><span style="color: #004600;">null</span> <span style="color: #008080;">then</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">left</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmap</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">left</span><span style="color: #0000FF;">],</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">rid</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
procedure main() |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">]!=</span><span style="color: #004600;">null</span> <span style="color: #008080;">then</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmap</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tree</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">],</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">rid</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
object root = newnode(1.00) |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">tree</span> |
|||
-- Add some nodes. |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
root[left] = newnode(1.10) |
|||
root[left][left] = newnode(1.11) |
|||
root[left][right] = newnode(1.12) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">newnode</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">)</span> |
|||
root[right] = newnode(1.20) |
|||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">v</span><span style="color: #0000FF;">,</span><span style="color: #004600;">null</span><span style="color: #0000FF;">,</span><span style="color: #004600;">null</span><span style="color: #0000FF;">}</span> |
|||
root[right][left] = newnode(1.21) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
root[right][right] = newnode(1.22) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">add10</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">10</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
|||
-- Now the tree has seven nodes. |
|||
<span style="color: #004080;">object</span> <span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newnode</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1.00</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">-- Add some nodes.</span> |
|||
<span style="color: #000000;">root</span><span style="color: #0000FF;">[</span><span style="color: #000000;">left</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newnode</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1.10</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">root</span><span style="color: #0000FF;">[</span><span style="color: #000000;">left</span><span style="color: #0000FF;">][</span><span style="color: #000000;">left</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newnode</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1.11</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">root</span><span style="color: #0000FF;">[</span><span style="color: #000000;">left</span><span style="color: #0000FF;">][</span><span style="color: #000000;">right</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newnode</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1.12</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">root</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newnode</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1.20</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">root</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">][</span><span style="color: #000000;">left</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newnode</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1.21</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000000;">root</span><span style="color: #0000FF;">[</span><span style="color: #000000;">right</span><span style="color: #0000FF;">][</span><span style="color: #000000;">right</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newnode</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1.22</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">-- Now the tree has seven nodes. |
|||
-- Show the whole tree.</span> |
|||
<span style="color: #7060A8;">ppOpt</span><span style="color: #0000FF;">({</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">root</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">-- Modify the whole tree.</span> |
|||
<span style="color: #000000;">root</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">root</span><span style="color: #0000FF;">,</span><span style="color: #000000;">add10</span><span style="color: #0000FF;">)</span> |
|||
-- |
<span style="color: #000080;font-style:italic;">-- Create a whole new tree.</span> |
||
<span style="color: #004080;">object</span> <span style="color: #000000;">root2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmap</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">root</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">newnode</span><span style="color: #0000FF;">)</span> |
|||
ppOpt({pp_Nest,2}) |
|||
pp(root) |
|||
-- |
<span style="color: #000080;font-style:italic;">-- Show the whole tree again.</span> |
||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">root</span><span style="color: #0000FF;">)</span> |
|||
root = tmap(root,routine_id("add10")) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span> |
|||
-- Show the whole tree again. |
|||
<!--</syntaxhighlight>--> |
|||
pp(root) |
|||
end procedure |
|||
main()</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 827: | Line 1,180: | ||
=={{header|PicoLisp}}== |
=={{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): |
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): |
||
< |
<syntaxhighlight lang="picolisp">(de mapTree (Tree Fun) |
||
(set Tree (Fun (car Tree))) |
(set Tree (Fun (car Tree))) |
||
(and (cadr Tree) (mapTree @ Fun)) |
(and (cadr Tree) (mapTree @ Fun)) |
||
(and (cddr Tree) (mapTree @ Fun)) )</ |
(and (cddr Tree) (mapTree @ Fun)) )</syntaxhighlight> |
||
Test: |
Test: |
||
<pre style="height:20em;overflow:scroll">(balance 'MyTree (range 1 7)) # Create a tree of numbers |
<pre style="height:20em;overflow:scroll">(balance 'MyTree (range 1 7)) # Create a tree of numbers |
||
Line 886: | Line 1,239: | ||
-> NIL</pre> |
-> NIL</pre> |
||
=={{header| |
=={{header|Prolog}}== |
||
{{works with|SWI Prolog}} |
|||
SWI-Prolog does not support object-oriented programming, but we can simulate it. |
|||
<syntaxhighlight lang="prolog">% Tree Definition |
|||
tree(leaf(_)). |
|||
tree(branch(Left, Right)) :- tree(Left), tree(Right). |
|||
% Definition of the addone function |
|||
Typed Racket has parametric polymorphism: |
|||
addone(X, Y) :- Y is X + 1. |
|||
% Definition of treewalk |
|||
<lang racket> |
|||
treewalk(leaf(Value), Func, leaf(NewValue)) :- call(Func, Value, NewValue). |
|||
treewalk(branch(Left, Right), Func, branch(NewLeft, NewRight)) :- |
|||
treewalk(Left, Func, NewLeft), |
|||
treewalk(Right, Func, NewRight). |
|||
% Execution |
|||
run :- |
|||
X = branch(leaf(2), branch(leaf(3),leaf(4))), |
|||
treewalk(X, addone, Y), |
|||
write(Y).</syntaxhighlight> |
|||
=={{header|Racket}}== |
|||
Typed Racket has parametric polymorphism: |
|||
<syntaxhighlight lang="racket"> |
|||
#lang typed/racket |
#lang typed/racket |
||
Line 911: | Line 1,284: | ||
(tree-map add1 (Node 5 (Node 3 #f #f) #f)) |
(tree-map add1 (Node 5 (Node 3 #f #f) #f)) |
||
(Node 6 (Node 4 #f #f) #f)) |
(Node 6 (Node 4 #f #f) #f)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo|2020.08.1}} |
|||
<syntaxhighlight lang="raku" line>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;</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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]))</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
This REXX programming example is modeled after the '''D''' example. |
This REXX programming example is modeled after the '''D''' example. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program demonstrates (with displays) a method of parametric polymorphism. */ |
||
call newRoot 1.00, 3 /*new root, and also indicate 3 stems.*/ |
call newRoot 1.00, 3 /*new root, and also indicate 3 stems.*/ |
||
/* [↓] no need to label the stems. */ |
/* [↓] no need to label the stems. */ |
||
Line 929: | Line 1,328: | ||
exit /*stick a fork in it, we're all done. */ |
exit /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
addStem: nodes=nodes+1; |
addStem: nodes= nodes + 1; do j=1 for stems; root.nodes.j= arg(1); end; return |
||
newRoot: parse arg @,stems; nodes= -1; call addStem copies('═',9); call addStem @; return |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
modRoot: |
modRoot: arg #; do j=1 for nodes /*traipse through all the defined nodes*/ |
||
do k=1 for stems |
do k=1 for stems /*add bias ──►───────────────────────┐ */ |
||
if datatype(root.j.k, 'N') then root.j.k=root.j.k + |
if datatype(root.j.k, 'N') then root.j.k= root.j.k + # /* ◄───┘ */ |
||
end /*k*/ |
end /*k*/ /* [↑] add if stem value is numeric.*/ |
||
end /*j*/ |
end /*j*/ |
||
return |
return |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
sayNodes: w= 9; do j=0 to nodes; _= /*ensure each of the nodes gets shown. */ |
|||
do k=1 for stems; _= _ center(root.j.k, w) /*concatenate a node.*/ |
|||
end /*k*/ |
|||
$= word('node='j, 1 + (j<1) ) /*define a label for this line's output*/ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
say center($, w) substr(_, 2) /*ignore 1st (leading) blank which was */ |
|||
end /*j*/ /* [↑] caused by concatenation.*/ |
|||
say /*show a blank line to separate outputs*/ |
|||
return</syntaxhighlight> |
|||
say substr(_, 2) /*ignore the first (leading) blank. */ |
|||
end /*j*/ |
|||
say left('', stems*11) || '('nodes" nodes)" /*also show number of nodes.*/ |
|||
return</lang> |
|||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input:}} |
||
<pre> |
<pre> |
||
═════════ ═════════ ═════════ |
═════════ ═════════ ═════════ |
||
1.00 1.00 1.00 |
node=1 1.00 1.00 1.00 |
||
1.10 1.10 1.10 |
node=2 1.10 1.10 1.10 |
||
1.11 1.11 1.11 |
node=3 1.11 1.11 1.11 |
||
1.12 1.12 1.12 |
node=4 1.12 1.12 1.12 |
||
1.20 1.20 1.20 |
node=5 1.20 1.20 1.20 |
||
1.21 1.21 1.21 |
node=6 1.21 1.21 1.21 |
||
1.22 1.22 1.22 |
node=7 1.22 1.22 1.22 |
||
(7 nodes) |
|||
═════════ ═════════ ═════════ |
═════════ ═════════ ═════════ |
||
51.00 51.00 51.00 |
node=1 51.00 51.00 51.00 |
||
51.10 51.10 51.10 |
node=2 51.10 51.10 51.10 |
||
51.11 51.11 51.11 |
node=3 51.11 51.11 51.11 |
||
51.12 51.12 51.12 |
node=4 51.12 51.12 51.12 |
||
51.20 51.20 51.20 |
node=5 51.20 51.20 51.20 |
||
51.21 51.21 51.21 |
node=6 51.21 51.21 51.21 |
||
51.22 51.22 51.22 |
node=7 51.22 51.22 51.22 |
||
(7 nodes) |
|||
</pre> |
</pre> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">struct TreeNode<T> { |
||
value: T, |
value: T, |
||
left: Option<Box<TreeNode<T>>>, |
left: Option<Box<TreeNode<T>>>, |
||
Line 1,019: | Line 1,413: | ||
let new_root = root.my_map(&|x| *x as f64 * 333.333f64); |
let new_root = root.my_map(&|x| *x as f64 * 333.333f64); |
||
new_root.my_map(&|x| { println!("{}" , x) }); |
new_root.my_map(&|x| { println!("{}" , x) }); |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
Line 1,026: | Line 1,420: | ||
the example in question: |
the example in question: |
||
< |
<syntaxhighlight lang="scala">case class Tree[+A](value: A, left: Option[Tree[A]], right: Option[Tree[A]]) { |
||
def map[B](f: A => B): Tree[B] = |
def map[B](f: A => B): Tree[B] = |
||
Tree(f(value), left map (_.map(f)), right map (_.map(f))) |
Tree(f(value), left map (_.map(f)), right map (_.map(f))) |
||
}</ |
}</syntaxhighlight> |
||
Note that the type parameter of the class <tt>Tree</tt>, <tt>[+A]</tt>. The |
Note that the type parameter of the class <tt>Tree</tt>, <tt>[+A]</tt>. The |
||
Line 1,035: | Line 1,429: | ||
will be a subtype of <tt>Tree[Y]</tt> if <tt>X</tt> is a subtype of <tt>Y</tt>. For example: |
will be a subtype of <tt>Tree[Y]</tt> if <tt>X</tt> is a subtype of <tt>Y</tt>. For example: |
||
< |
<syntaxhighlight lang="scala">class Employee(val name: String) |
||
class Manager(name: String) extends Employee(name) |
class Manager(name: String) extends Employee(name) |
||
val t = Tree(new Manager("PHB"), None, None) |
val t = Tree(new Manager("PHB"), None, None) |
||
val t2: Tree[Employee] = t</ |
val t2: Tree[Employee] = t</syntaxhighlight> |
||
The second assignment is legal because <tt>t</tt> is of type <tt>Tree[Manager]</tt>, and since |
The second assignment is legal because <tt>t</tt> is of type <tt>Tree[Manager]</tt>, and since |
||
Line 1,047: | Line 1,441: | ||
Another possible variance is the ''contra-variance''. For instance, consider the following example: |
Another possible variance is the ''contra-variance''. For instance, consider the following example: |
||
< |
<syntaxhighlight lang="scala">def toName(e: Employee) = e.name |
||
val treeOfNames = t.map(toName)</ |
val treeOfNames = t.map(toName)</syntaxhighlight> |
||
This works, even though <tt>map</tt> is expecting a function from <tt>Manager</tt> into something, |
This works, even though <tt>map</tt> is expecting a function from <tt>Manager</tt> into something, |
||
Line 1,055: | Line 1,449: | ||
definition in Scala: |
definition in Scala: |
||
< |
<syntaxhighlight lang="scala">trait Function1[-T1, +R]</syntaxhighlight> |
||
The minus sign indicates that this trait is ''contra-variant'' in <tt>T1</tt>, which happens to be |
The minus sign indicates that this trait is ''contra-variant'' in <tt>T1</tt>, which happens to be |
||
Line 1,066: | Line 1,460: | ||
Let's add another method to <tt>Tree</tt> to see another concept: |
Let's add another method to <tt>Tree</tt> to see another concept: |
||
< |
<syntaxhighlight lang="scala">case class Tree[+A](value: A, left: Option[Tree[A]], right: Option[Tree[A]]) { |
||
def map[B](f: A => B): Tree[B] = |
def map[B](f: A => B): Tree[B] = |
||
Tree(f(value), left map (_.map(f)), right map (_.map(f))) |
Tree(f(value), left map (_.map(f)), right map (_.map(f))) |
||
def find[B >: A](what: B): Boolean = |
def find[B >: A](what: B): Boolean = |
||
(value == what) || left.map(_.find(what)).getOrElse(false) || right.map(_.find(what)).getOrElse(false) |
(value == what) || left.map(_.find(what)).getOrElse(false) || right.map(_.find(what)).getOrElse(false) |
||
}</ |
}</syntaxhighlight> |
||
The type parameter of <tt>find</tt> is <tt>[B >: A]</tt>. That means the type is some <tt>B</tt>, as long |
The type parameter of <tt>find</tt> is <tt>[B >: A]</tt>. That means the type is some <tt>B</tt>, as long |
||
Line 1,077: | Line 1,471: | ||
accept it. To understand why, let's consider the following code: |
accept it. To understand why, let's consider the following code: |
||
< |
<syntaxhighlight lang="scala">if (t2.find(new Employee("Dilbert"))) |
||
println("Call Catbert!")</ |
println("Call Catbert!")</syntaxhighlight> |
||
Here we have <tt>find</tt> receiving an argument of type <tt>Employee</tt>, even though the tree |
Here we have <tt>find</tt> receiving an argument of type <tt>Employee</tt>, even though the tree |
||
Line 1,089: | Line 1,483: | ||
to be defined when a class is inherited. One simple example would be: |
to be defined when a class is inherited. One simple example would be: |
||
< |
<syntaxhighlight lang="scala">trait DFA { |
||
type Element |
type Element |
||
val map = new collection.mutable.HashMap[Element, DFA]() |
val map = new collection.mutable.HashMap[Element, DFA]() |
||
}</ |
}</syntaxhighlight> |
||
A concrete class wishing to inherit from <tt>DFA</tt> would need to define <tt>Element</tt>. Abstract |
A concrete class wishing to inherit from <tt>DFA</tt> would need to define <tt>Element</tt>. Abstract |
||
Line 1,107: | Line 1,501: | ||
When ''map'' is called ''aVariable'' is used also in the actual parameter of ''aFunc'': map(container1, num, num + 1) |
When ''map'' is called ''aVariable'' is used also in the actual parameter of ''aFunc'': map(container1, num, num + 1) |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const func type: container (in type: elemType) is func |
const func type: container (in type: elemType) is func |
||
Line 1,143: | Line 1,537: | ||
end for; |
end for; |
||
writeln; |
writeln; |
||
end func;</ |
end func;</syntaxhighlight> |
||
Output: |
Output: |
||
Line 1,151: | Line 1,545: | ||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
< |
<syntaxhighlight lang="sml">datatype 'a tree = Empty | Node of 'a * 'a tree * 'a tree |
||
(** val map_tree = fn : ('a -> 'b) -> 'a tree -> 'b tree *) |
(** val map_tree = fn : ('a -> 'b) -> 'a tree -> 'b tree *) |
||
fun map_tree f Empty = Empty |
fun map_tree f Empty = Empty |
||
| map_tree f (Node (x,l,r)) = Node (f x, map_tree f l, map_tree f r)</ |
| map_tree f (Node (x,l,r)) = Node (f x, map_tree f l, map_tree f r)</syntaxhighlight> |
||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="swift">class Tree<T> { |
||
var value: T? |
var value: T? |
||
var left: Tree<T>? |
var left: Tree<T>? |
||
Line 1,169: | Line 1,563: | ||
right?.replaceAll(value) |
right?.replaceAll(value) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Another version based on Algebraic Data Types: |
Another version based on Algebraic Data Types: |
||
{{works with|Swift|2+}} |
{{works with|Swift|2+}} |
||
< |
<syntaxhighlight lang="swift">enum Tree<T> { |
||
case Empty |
case Empty |
||
indirect case Node(T, Tree<T>, Tree<T>) |
indirect case Node(T, Tree<T>, Tree<T>) |
||
Line 1,183: | Line 1,577: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
Line 1,189: | Line 1,583: | ||
routinely. A parameterized binary tree type can be defined using a syntax for anonymous |
routinely. A parameterized binary tree type can be defined using a syntax for anonymous |
||
recursion in type expressions as in this example, |
recursion in type expressions as in this example, |
||
< |
<syntaxhighlight lang="ursala">binary_tree_of "node-type" = "node-type"%hhhhWZAZ</syntaxhighlight> |
||
or by way of a recurrence solved using a fixed point combinator imported from a library |
or by way of a recurrence solved using a fixed point combinator imported from a library |
||
as shown below. |
as shown below. |
||
< |
<syntaxhighlight lang="ursala">#import tag |
||
#fix general_type_fixer 1 |
#fix general_type_fixer 1 |
||
binary_tree_of "node-type" = ("node-type",(binary_tree_of "node-type")%Z)%drWZwlwAZ</ |
binary_tree_of "node-type" = ("node-type",(binary_tree_of "node-type")%Z)%drWZwlwAZ</syntaxhighlight> |
||
(The <code>%Z</code> type operator constructs a "maybe" type, i.e., the free union of its operand type |
(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 |
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. |
point-free form. |
||
< |
<syntaxhighlight lang="ursala">binary_tree_of = %-hhhhWZAZ</syntaxhighlight> |
||
A mapping combinator over this type can be defined with pattern matching like this |
A mapping combinator over this type can be defined with pattern matching like this |
||
< |
<syntaxhighlight lang="ursala">binary_tree_map "f" = ~&a^& ^A/"f"@an ~&amPfamPWB</syntaxhighlight> |
||
or in point free form like this. |
or in point free form like this. |
||
< |
<syntaxhighlight lang="ursala">binary_tree_map = ~&a^&+ ^A\~&amPfamPWB+ @an</syntaxhighlight> |
||
Here is a test program |
Here is a test program |
||
defining a type of binary trees of strings, and a function that concatenates each node |
defining a type of binary trees of strings, and a function that concatenates each node |
||
with itself. |
with itself. |
||
< |
<syntaxhighlight lang="ursala">string_tree = binary_tree_of %s |
||
x = 'foo': ('bar': (),'baz': ()) |
x = 'foo': ('bar': (),'baz': ()) |
||
Line 1,214: | Line 1,608: | ||
#cast string_tree |
#cast string_tree |
||
example = (binary_tree_map "s". "s"--"s") x</ |
example = (binary_tree_map "s". "s"--"s") x</syntaxhighlight> |
||
Type signatures are not necessarily associated with function declarations, but |
Type signatures are not necessarily associated with function declarations, but |
||
have uses in the other contexts such as assertions and compiler directives |
have uses in the other contexts such as assertions and compiler directives |
||
Line 1,221: | Line 1,615: | ||
'foofoo': ('barbar': (),'bazbaz': ()) |
'foofoo': ('barbar': (),'bazbaz': ()) |
||
</pre> |
</pre> |
||
=={{header|Visual Basic .NET}}== |
|||
{{trans|C# modern version}} |
|||
<syntaxhighlight lang="vbnet">Class BinaryTree(Of T) |
|||
ReadOnly Property Left As BinaryTree(Of T) |
|||
ReadOnly Property Right As BinaryTree(Of T) |
|||
ReadOnly Property Value As T |
|||
Sub New(value As T, Optional left As BinaryTree(Of T) = Nothing, Optional right As BinaryTree(Of T) = Nothing) |
|||
Me.Value = value |
|||
Me.Left = left |
|||
Me.Right = right |
|||
End Sub |
|||
Function Map(Of U)(f As Func(Of T, U)) As BinaryTree(Of U) |
|||
Return New BinaryTree(Of U)(f(Me.Value), Me.Left?.Map(f), Me.Right?.Map(f)) |
|||
End Function |
|||
Overrides Function ToString() As String |
|||
Dim sb As New Text.StringBuilder() |
|||
Me.ToString(sb, 0) |
|||
Return sb.ToString() |
|||
End Function |
|||
Private Overloads Sub ToString(sb As Text.StringBuilder, depth As Integer) |
|||
sb.Append(New String(ChrW(AscW(vbTab)), depth)) |
|||
sb.AppendLine(Me.Value?.ToString()) |
|||
Me.Left?.ToString(sb, depth + 1) |
|||
Me.Right?.ToString(sb, depth + 1) |
|||
End Sub |
|||
End Class |
|||
Module Program |
|||
Sub Main() |
|||
Dim b As New BinaryTree(Of Integer)(6, New BinaryTree(Of Integer)(5), New BinaryTree(Of Integer)(7)) |
|||
Dim b2 As BinaryTree(Of Double) = b.Map(Function(x) x * 0.5) |
|||
Console.WriteLine(b) |
|||
Console.WriteLine(b2) |
|||
End Sub |
|||
End Module</syntaxhighlight> |
|||
{{out}} |
|||
<pre>6 |
|||
5 |
|||
7 |
|||
3 |
|||
2.5 |
|||
3.5</pre> |
|||
=={{header|Visual Prolog}}== |
=={{header|Visual Prolog}}== |
||
< |
<syntaxhighlight lang="prolog"> |
||
domains |
domains |
||
tree{Type} = branch(tree{Type} Left, tree{Type} Right); leaf(Type Value). |
tree{Type} = branch(tree{Type} Left, tree{Type} Right); leaf(Type Value). |
||
Line 1,243: | Line 1,686: | ||
write(Y), |
write(Y), |
||
succeed(). |
succeed(). |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Wren}}== |
|||
{{trans|Kotlin}} |
|||
Wren is dynamically type and so doesn't have parametric polymorphism (PP) as such; in a sense every method or function is polymorphic over its parameters. |
|||
However, that doesn't mean that type safety is unimportant and, in the case of a Binary Tree, we'd generally want all its nodes to contain values of the same type. |
|||
Fortunately, we can simulate PP by passing an extra parameter to a collection class's contructor to specify the type of values to be used for that particular instantiation. We can then use this to guard against the wrong type of values being passed to the class's other methods. |
|||
<syntaxhighlight lang="wren">class BinaryTree { |
|||
construct new(T, value) { |
|||
if (!(T is Class)) Fiber.abort ("T must be a class.") |
|||
if (value.type != T) Fiber.abort("Value must be of type T.") |
|||
_kind = T |
|||
_value = value |
|||
_left = null |
|||
_right = null |
|||
} |
|||
// constructor overload to enable kind to be inferred from type of value |
|||
static new (value) { new(value.type, value) } |
|||
kind { _kind } |
|||
value { _value} |
|||
value=(v) { |
|||
if (v.type != _kind) Fiber.abort("Value must be of type %(_kind)") |
|||
_value = v |
|||
} |
|||
left { _left } |
|||
right { _right } |
|||
left=(b) { |
|||
if (b.type != BinaryTree || b.kind != _kind) { |
|||
Fiber.abort("Argument must be a BinaryTree of type %(_kind)") |
|||
} |
|||
_left = b |
|||
} |
|||
right=(b) { |
|||
if (b.type != BinaryTree || b.kind != _kind) { |
|||
Fiber.abort("Argument must be a BinaryTree of type %(_kind)") |
|||
} |
|||
_right = b |
|||
} |
|||
map(f) { |
|||
var tree = BinaryTree.new(f.call(_value)) |
|||
if (_left) tree.left = left.map(f) |
|||
if (_right) tree.right = right.map(f) |
|||
return tree |
|||
} |
|||
showTopThree() { "(%(left.value), %(value), %(right.value))" } |
|||
} |
|||
var b = BinaryTree.new(6) |
|||
b.left = BinaryTree.new(5) |
|||
b.right = BinaryTree.new(7) |
|||
System.print(b.showTopThree()) |
|||
var b2 = b.map{ |i| i * 10 } |
|||
System.print(b2.showTopThree()) |
|||
b2.value = "six" // generates an error because "six" is not a Num</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
(5, 6, 7) |
|||
(50, 60, 70) |
|||
Value must be of type Num |
|||
[./parametric_polymorphism line 17] in value=(_) |
|||
[./parametric_polymorphism line 53] in (script) |
|||
</pre> |
|||
Line 1,252: | Line 1,766: | ||
{{omit from|Axe}} |
{{omit from|Axe}} |
||
{{omit from|Bc|no types in bc}} |
|||
{{omit from|C|no type variables in stdc}} |
{{omit from|C|no type variables in stdc}} |
||
{{omit from|C|no type variables}} |
{{omit from|C|no type variables}} |
||
{{omit from|Dc|no types in dc}} |
|||
{{omit from|Factor|not statically typed}} |
|||
{{omit from|J|not statically typed}} |
{{omit from|J|not statically typed}} |
||
{{omit from|JavaScript|not statically typed}} |
{{omit from|JavaScript|not statically typed}} |
||
Line 1,267: | Line 1,784: | ||
{{omit from|LaTeX}} |
{{omit from|LaTeX}} |
||
{{omit from|Retro|typeless}} |
{{omit from|Retro|typeless}} |
||
{{omit from|VBA|the Variant type is available.}} |
|||
{{omit from|zkl|typeless}} |
{{omit from|zkl|typeless}} |
Latest revision as of 20:52, 2 July 2024
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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.
- Task
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
If the goal is to separate algorithms from types at compile time, C may do it by macros. Here's sample code implementing binary tree with node creation and insertion:
#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;
}
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#
using System;
class BinaryTree<T>
{
public T value;
public BinaryTree<T> left;
public BinaryTree<T> right;
public BinaryTree(T value)
{
this.value = value;
}
public BinaryTree<U> Map<U>(Func<T, U> f)
{
BinaryTree<U> tree = new BinaryTree<U>(f(this.value));
if (this.left != null)
{
tree.left = this.left.Map(f);
}
if (this.right != null)
{
tree.right = this.right.Map(f);
}
return tree;
}
}
Creating a tree of integers and using Map to generate a tree of doubles with every node half the value of the first:
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 * 0.5);
}
}
A version using more modern language constructs:
using System;
class BinaryTree<T>
{
public BinaryTree<T> Left { get; }
public BinaryTree<T> Right { get; }
public T Value { get; }
public BinaryTree(T value, BinaryTree<T> left = null, BinaryTree<T> right = null)
{
this.Value = value;
this.Left = left;
this.Right = right;
}
public BinaryTree<U> Map<U>(Func<T, U> f)
{
return new BinaryTree<U>(f(this.Value), this.Left?.Map(f), this.Right?.Map(f));
}
public override string ToString()
{
var sb = new System.Text.StringBuilder();
this.ToString(sb, 0);
return sb.ToString();
}
private void ToString(System.Text.StringBuilder sb, int depth)
{
sb.Append(new string('\t', depth));
sb.AppendLine(this.Value?.ToString());
this.Left?.ToString(sb, depth + 1);
this.Right?.ToString(sb, depth + 1);
}
}
static class Program
{
static void Main()
{
var b = new BinaryTree<int>(6, new BinaryTree<int>(5), new BinaryTree<int>(7));
BinaryTree<double> b2 = b.Map(x => x * 0.5);
Console.WriteLine(b);
Console.WriteLine(b2);
}
}
- Output:
6 5 7 3 2.5 3.5
C++
template<typename 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;
if (left != nullptr)
left->replace_all(new_value);
if (right != nullptr)
right->replace_all(new_value);
}
C3
module tree(<Type>);
struct Tree
{
Type value;
Tree* left;
Tree* right;
}
fn void Tree.replace_all(&self, Type new_value)
{
self.value = new_value;
if (self.left) self.left.replace_all(new_value);
if (self.right) self.right.replace_all(new_value);
}
Usage:
import tree;
fn void test()
{
Tree(<int>) inttree;
inttree.replace_all(3);
}
Ceylon
class BinaryTree<Data>(shared Data data, shared BinaryTree<Data>? left = null, shared BinaryTree<Data>? 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);
}
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)
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
fmap
in an instance of theFunctor
type class:instance Functor Tree where fmap f Empty = Empty fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)
fmap
can then be used exactly wheremapTree
can, but doing this also allows the use ofTree
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:add1Everywhere :: (f a) -> (f a) | Functor f & Num a add1Everywhere nums = fmap (\x = x + 1) numsIf we have a tree of integers, i.e. f is
Tree
and a isInteger
, then the type ofadd1Everywhere
isTree Integer -> Tree Integer
.
COBOL
>>SOURCE FORMAT IS FREE
IDENTIFICATION DIVISION.
CLASS-ID. Tree INHERITS FROM Base USING X.
DATE-WRITTEN. 20240702.
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
OBJECT-COMPUTER.
MEMORY SIZE IS 1073741824 CHARACTERS.
REPOSITORY.
CLASS Base.
CLASS X.
IDENTIFICATION DIVISION.
OBJECT.
DATA DIVISION.
WORKING-STORAGE SECTION.
77 ws-value USAGE IS OBJECT REFERENCE X ONLY.
77 ws-left USAGE IS OBJECT REFERENCE Tree ONLY.
77 ws-right USAGE IS OBJECT REFERENCE Tree ONLY.
PROCEDURE DIVISION.
IDENTIFICATION DIVISION.
METHOD-ID. replace_all.
DATA DIVISION.
LINKAGE SECTION.
77 new_value USAGE IS OBJECT REFERENCE X ONLY.
PROCEDURE DIVISION USING BY REFERENCE new_value.
MOVE new_value TO ws-value.
IF ws-left IS NOT EQUAL TO NULL THEN
INVOKE ws-left "replace_all" USING BY REFERENCE new_value.
IF ws-right IS NOT EQUAL TO NULL THEN
INVOKE ws-right "replace_all" USING BY REFERENCE new_value.
GOBACK.
END METHOD replace_all.
END OBJECT.
END CLASS Tree.
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
.
(deftype pair (&key (car 't) (cdr 't))
`(cons ,car ,cdr))
Example
> (typep (cons 1 2) '(pair :car number :cdr number)) T
> (typep (cons 1 2) '(pair :car number :cdr character)) NIL
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));
}
- 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
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);
}
- 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.)
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
}
? 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>
FreeBASIC
FreeBASIC does not support object-oriented programming, so we will use a more procedural approach.
Type BinaryTree
valor As Integer
izda As BinaryTree Ptr
dcha As BinaryTree Ptr
End Type
Sub PrintTree(t As BinaryTree Ptr, depth As Integer)
If t = 0 Then Exit Sub
Print String(depth, Chr(9)); t->valor
PrintTree(t->izda, depth + 1)
PrintTree(t->dcha, depth + 1)
End Sub
Dim As BinaryTree b = Type(6)
Dim As BinaryTree bLeft = Type(5)
Dim As BinaryTree bRight = Type(7)
b.izda = @bLeft
b.dcha = @bRight
PrintTree(@b, 0)
F#
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))
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)
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 X = A + B*C
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.
However, with F90 came the MODULE protocol with facilities suitable for defining "generic" subroutines or functions, or so it appears:
MODULE SORTSEARCH !Genuflect towards Prof. D. Knuth.
INTERFACE FIND !Binary chop search, not indexed.
MODULE PROCEDURE
1 FINDI4, !I: of integers.
2 FINDF4,FINDF8, !F: of numbers.
3 FINDTTI2,FINDTTI4 !T: of texts.
END INTERFACE FIND
CONTAINS
INTEGER FUNCTION FINDI4(THIS,NUMB,N) !Binary chopper. Find i such that THIS = NUMB(i)
USE ASSISTANCE !Only for the trace stuff.
INTENT(IN) THIS,NUMB,N !Imply read-only, but definitely no need for any "copy-back".
INTEGER*4 THIS,NUMB(1:*) !Where is THIS in array NUMB(1:N)?
INTEGER N !The count. In other versions, it is supplied by the index.
INTEGER L,R,P !Fingers.
Chop away.
L = 0 !Establish outer bounds.
R = N + 1 !One before, and one after, the first and last.
1 P = (R - L)/2 !Probe point offset. Beware integer overflow with (L + R)/2.
IF (P.LE.0) THEN !Aha! Nowhere! And THIS follows NUMB(L).
FINDI4 = -L !Having -L rather than 0 (or other code) might be of interest.
RETURN !Finished.
END IF !So much for exhaustion.
P = P + L !Convert from offset to probe point.
IF (THIS - NUMB(P)) 3,4,2 !Compare to the probe point.
2 L = P !Shift the left bound up: THIS follows NUMB(P).
GO TO 1 !Another chop.
3 R = P !Shift the right bound down: THIS precedes NUMB(P).
GO TO 1 !Try again.
Caught it! THIS = NUMB(P)
4 FINDI4 = P !So, THIS is found, here!
END FUNCTION FINDI4 !On success, THIS = NUMB(FINDI4); no fancy index here...
END MODULE SORTSEARCH
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 INTEGER*4 THIS,NUMB(1:*)
need be changed, say to REAL*4 THIS,NUMB(1:*)
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.
That said, some systems had polymorphic variables, such as the B6700 whereby integers were represented as floating-point numbers and so exactly the same function could be presented with an integer or a floating-point variable (provided the compiler didn't check for parameter type matching - but this was routine) and it would work - so long as no divisions were involved since addition, subtraction, and multiplication are the same for both, but integer division discards any remainders. More recent computers following the Intel 8087 floating-point processor and similar add novel states to the scheme for floating-point arithmetic: not just zero and "gradual underflow" but "Infinity" and "Not a Number", which last violates even more of the axia of mathematics in that NaN does not equal NaN. In turn, this forces a modicum of polymorphism into the language so as to contend with the additional features, such as the special function IsNaN(x).
More generally, using the same code for different types of variable can be problematical. A scheme that works in single precision may not work in double precision (or vice-versa) or may not give corresponding levels of accuracy, or not converge at all, etc. While F90 also standardised special functions that give information about the precision of variables and the like, and in principle, a method could be coded that, guided by such information, would work for different precisions, this sort of scheme is beset by all manner of difficulties in problems more complex than the simple examples of text books.
Polymorphism just exacerbates the difficulties, thus, on page 219 of 16-Bit Modern Microcomputers by G. M. Corsline appears the remark "At least some of the generalized numerical solutions to common mathematical procedures have coding that is so involved and tricky in order to take care of all possible roundoff contingencies that they have been termed 'pornographic algorithms'.". And "Mathematical software is easy for the uninitiated to write but notoriously hard for the expert. This paradox exists because the beginner is satisfied if his code usually works in his own machine while the expert attempts, against overwhelming obstacles, to produce programs that always work on a large number of computers. The problem is that while standard formulas of mathematics are fairly easy to translate into FORTRAN they often are subject to instabilities due to roundoff error." - quoting John Palmer, 1980, Intel Corporation.
But sometimes it is not so troublesome, as in Pathological_floating_point_problems#The_Chaotic_Bank_Society whereby the special EPSILON(x) function that reports on the precision of a nominated variable of type x is used to determine the point beyond which further calculation (in that precision, for that formula) will make no difference.
Having flexible facilities available my lead one astray. Consider the following data aggregate, as became available with F90:
TYPE STUFF
INTEGER CODE !A key number.
CHARACTER*6 NAME !Associated data.
INTEGER THIS !etc.
END TYPE STUFF
TYPE(STUFF) TABLE(600) !An array of such entries.
Suppose the array was in sorted order by each entry's value of CODE so that TABLE(1).CODE <= TABLE(2).CODE, etc. and one wished to find the index of an entry with a specific value, x, of CODE. It is pleasing to be able to write FIND(x,TABLE.CODE,N)
and have it accepted by the compiler. Rather less pleasing is that it runs very slowly.
This is because consecutive elements in an array are expected to occupy consecutive locations in storage, but the CODE elements do not, being separated by the other elements of the aggregate. So, the compiler generates code to copy the required elements to a work area, presents that as the actual parameter, and copies from the work area back on return from the function, thereby vitiating the speed advantages of the binary search. This is why the INTENT(IN)
might help in such situations, as will writing FIND(x,TABLE(1:N).CODE,N)
should N be often less than the full size of the table. But really, in-line code for each such usage is the only answer, despite the lack of a pre-processor to generate it.
Other options are to remain with the older-style of Fortran, using separately-defined arrays having a naming convention such as TABLECODE(600), TABLENAME(600), etc. thus not gaining the unity of declaring a TYPE, or, declaring the size within the type as in INTEGER CODE(600)
except that this means that the size is a part of the type and different-sized tables would require different types, or, perhaps the compiler will handle this problem by passing a "stride" value for every array dimension so that subroutines and functions can index such parameters properly - at the cost of yet more overhead for parameter passing, and more complex indexing calculations.
In short, the available polymorphism whereby a parameter can be a normal array, or, an array-like "selection" of a component from an array of compound entities enables appealing syntax, but disasterous performance.
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.)
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)
}
}
Output:
binary tree average: 2.6666666666666665 b-tree average: 5
Alternatively, if generics are introduced into Go based on the current design, this is how the C++ example might look if translated to Go:
package rosettacode
type Tree(type T) struct {
val T
left *Tree(T)
right *Tree(T)
}
func (t *Tree(T)) ReplaceAll(rep T) {
t.val = rep
if t.left != nil { t.left.ReplaceAll(rep) }
if t.right != nil { t.right.ReplaceAll(rep) }
}
Groovy
(more or less)
Solution:
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)
}
}
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)
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
fmap
in an instance of theFunctor
type class:instance Functor Tree where fmap f Empty = Empty fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)
fmap
can then be used exactly wheremapTree
can, but doing this also allows the use ofTree
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:add1Everywhere :: (Functor f, Num a) => f a -> f a add1Everywhere nums = fmap (\x -> x + 1) numsIf we have a tree of integers, i.e. f is
Tree
and a isInteger
, then the type ofadd1Everywhere
isTree Integer -> Tree Integer
.
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.
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
Inform 7
Phrases (the equivalent of global functions) can be defined with type parameters:
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.
Inform 7 does not allow user-defined parametric types. Some built-in types can be parameterized, though:
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
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:
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);
}
}
Julia
module BinaryTrees
mutable struct BinaryTree{V}
v::V
l::Union{BinaryTree{V}, Nothing}
r::Union{BinaryTree{V}, Nothing}
end
BinaryTree(v) = BinaryTree(v, nothing, nothing)
map(f, bt::BinaryTree) = BinaryTree(f(bt.v), map(f, bt.l), map(f, bt.r))
map(f, bt::Nothing) = nothing
let inttree = BinaryTree(
0,
BinaryTree(
1,
BinaryTree(3),
BinaryTree(5),
),
BinaryTree(
2,
BinaryTree(4),
nothing,
),
)
map(x -> 2x^2, inttree)
end
let strtree = BinaryTree(
"hello",
BinaryTree(
"world!",
BinaryTree("Julia"),
nothing,
),
BinaryTree(
"foo",
BinaryTree("bar"),
BinaryTree("baz"),
),
)
map(uppercase, strtree)
end
end
Kotlin
// version 1.0.6
class BinaryTree<T>(var value: T) {
var left : BinaryTree<T>? = null
var right: BinaryTree<T>? = null
fun <U> map(f: (T) -> U): BinaryTree<U> {
val tree = BinaryTree<U>(f(value))
if (left != null) tree.left = left?.map(f)
if (right != null) tree.right = right?.map(f)
return tree
}
fun showTopThree() = "(${left?.value}, $value, ${right?.value})"
}
fun main(args: Array<String>) {
val b = BinaryTree(6)
b.left = BinaryTree(5)
b.right = BinaryTree(7)
println(b.showTopThree())
val b2 = b.map { it * 10.0 }
println(b2.showTopThree())
}
- Output:
(5, 6, 7) (50.0, 60.0, 70.0)
Mathematica /Wolfram Language
The Wolfram language is naturally polymorphic. Function can (generally) accept any type. Here an example to join two lists of with different types and an example of squaring an input:
f[a_] := Join[a, a]
f[{1, 2, 3}]
f[{"1", "2", "3"}]
f[{1.1, 2.1, 3.1}]
f[G[1, "a", Pi]]
g[x_] := x^2
g[2]
g[3.5]
g[Pi]
g["a"]
- Output:
{1,2,3,1,2,3} {1,2,3,1,2,3} {1.1,2.1,3.1,1.1,2.1,3.1} G[1,a,\[Pi],1,a,\[Pi]] 4 12.25 \[Pi]^2 (a)^2
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)).
Nim
import strutils, sugar
type Tree[T] = ref object
value: T
left, right: Tree[T]
proc newTree[T](value = default(T)): Tree[T] =
## Create a tree with a single node with the given value.
Tree[T](value: value)
proc map[T, U](tree: Tree[T]; f: (T) -> U): Tree[U] =
## Apply function "f" to each element of a tree, building
## another tree.
result = newTree[U](f(tree.value))
if not tree.left.isNil:
result.left = tree.left.map(f)
if not tree.right.isNil:
result.right = tree.right.map(f)
proc print(tree: Tree; indent = 0) =
## Print a tree.
let start = repeat(' ', indent)
echo start, "value: ", tree.value
if tree.left.isNil:
echo start, " nil"
else:
print(tree.left, indent + 2)
if tree.right.isNil:
echo start, " nil"
else:
print(tree.right, indent + 2)
when isMainModule:
echo "Initial tree:"
var tree = newTree[int](5)
tree.left = newTree[int](2)
tree.right = newTree[int](7)
print(tree)
echo ""
echo "Tree created by applying a function to each node:"
let tree1 = tree.map((x) => 1 / x)
print(tree1)
- Output:
Initial tree: value: 5 value: 2 nil nil value: 7 nil nil Tree created by applying a function to each node: value: 0.2 value: 0.5 nil nil value: 0.1428571428571428 nil nil
Objective-C
@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
Note that the generic type variable is only used in the declaration, but not in the implementation.
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)
PascalABC.NET
type Node<T> = auto class
data: T;
left,right: Node<T>;
end;
function CreateTree(n: integer): Node<integer>;
begin
if n = 0 then
Result := nil
else
Result := new Node<integer>(
Random(100),
CreateTree((n-1) div 2),
CreateTree(n-1 - (n-1) div 2)
);
end;
procedure InfixTraverse<T>(root: Node<T>; act: T -> ());
begin
if root = nil then
exit;
InfixTraverse(root.left,act);
act(root.data);
InfixTraverse(root.right,act);
end;
begin
var tree := CreateTree(10);
Println(tree);
InfixTraverse(tree, x -> Print(x));
end.
- Output:
(58,(52,(3,nil,nil),(35,nil,(25,nil,nil))),(29,(3,nil,(50,nil,nil)),(2,nil,(86,nil,nil)))) 3 52 35 25 58 3 50 29 2 86
Phix
Phix is naturally polymorphic, with optional static typing.
The standard builtin type hierarcy is trivial:
<-------- object ---------> | | +-atom +-sequence | | +-integer +-string
User defined types are subclasses of those.
If you declare a parameter as type integer then obviously it is optimised for that, and crashes when given something else (with a clear human-readable message and file name/line number).
If you declare a parameter as type object then it can handle anything you can throw at it - integers, floats, strings, or (deeply) nested sequences.
Of course many builtin routines are naturally generic, such as sort and print.
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:
?sort(shuffle({5,"oranges",6,"apples",7}))
- Output:
{5,6,7,"apples","oranges"}
For comparison purposes (and because this entry looked a bit sparse without it) this is the D example from this page translated to Phix.
Note that tmap has to be a function rather than a procedure with a reference parameter, but this still achieves
pass-by-reference/in-situ updates, mainly because root is a local rather than global/static, and is the target of
(aka assigned to/overwritten on return from) the top-level tmap() call, and yet also manages the C#/Dart/Kotlin
thing (by which I am referring to those specific examples on this page) of creating a whole new tree, simply
because lhs assignee!=rhs reference (aka root2!=root) in "root2 = tmap(root,rid)", not that such a "deep clone"
would (barring a few dirty low-level tricks) behave any differently to "root2=root", which is "a straightforward shared reference
with cow semantics". Aside: this example lost a little bit of it's charm when the deep_copy() had to go in to make it pwa/p2js compatible, which has somewhat negated the previous sentence, but that was happening implicitly anyway, and the depths of 1 (ie ",1" on the deep_copy()) retain similar efficiency.
with javascript_semantics enum data, left, right function tmap(sequence tree, integer rid) tree[data] = rid(tree[data]) if tree[left]!=null then tree[left] = tmap(deep_copy(tree[left],1),rid) end if if tree[right]!=null then tree[right] = tmap(deep_copy(tree[right],1),rid) end if return tree end function function newnode(object v) return {v,null,null} end function function add10(atom x) return x+10 end function procedure main() object root = newnode(1.00) -- Add some nodes. root[left] = newnode(1.10) root[left][left] = newnode(1.11) root[left][right] = newnode(1.12) root[right] = newnode(1.20) root[right][left] = newnode(1.21) root[right][right] = newnode(1.22) -- Now the tree has seven nodes. -- Show the whole tree. ppOpt({pp_Nest,2}) pp(root) -- Modify the whole tree. root = tmap(root,add10) -- Create a whole new tree. object root2 = tmap(deep_copy(root,1),newnode) -- Show the whole tree again. pp(root) end procedure main()
- Output:
{1, {1.1, {1.11,0,0}, {1.12,0,0}}, {1.2, {1.21,0,0}, {1.22,0,0}}} {11, {11.1, {11.11,0,0}, {11.12,0,0}}, {11.2, {11.21,0,0}, {11.22,0,0}}}
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):
(de mapTree (Tree Fun)
(set Tree (Fun (car Tree)))
(and (cadr Tree) (mapTree @ Fun))
(and (cddr Tree) (mapTree @ Fun)) )
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" -> NIL
Prolog
SWI-Prolog does not support object-oriented programming, but we can simulate it.
% Tree Definition
tree(leaf(_)).
tree(branch(Left, Right)) :- tree(Left), tree(Right).
% Definition of the addone function
addone(X, Y) :- Y is X + 1.
% Definition of treewalk
treewalk(leaf(Value), Func, leaf(NewValue)) :- call(Func, Value, NewValue).
treewalk(branch(Left, Right), Func, branch(NewLeft, NewRight)) :-
treewalk(Left, Func, NewLeft),
treewalk(Right, Func, NewRight).
% Execution
run :-
X = branch(leaf(2), branch(leaf(3),leaf(4))),
treewalk(X, addone, Y),
write(Y).
Racket
Typed Racket has parametric polymorphism:
#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))
Raku
(formerly Perl 6)
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;
- 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]))
REXX
This REXX programming example is modeled after the D example.
/*REXX program demonstrates (with displays) a method of parametric polymorphism. */
call newRoot 1.00, 3 /*new root, and also indicate 3 stems.*/
/* [↓] no need to label the stems. */
call addStem 1.10 /*a 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 some nicely formatted values.*/
call modRoot 50 /*modRoot will add fifty to all stems. */
call sayNodes /*display some nicely formatted values.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
addStem: nodes= nodes + 1; do j=1 for stems; root.nodes.j= arg(1); end; return
newRoot: parse arg @,stems; nodes= -1; call addStem copies('═',9); call addStem @; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
modRoot: arg #; do j=1 for nodes /*traipse through all the defined nodes*/
do k=1 for stems /*add bias ──►───────────────────────┐ */
if datatype(root.j.k, 'N') then root.j.k= root.j.k + # /* ◄───┘ */
end /*k*/ /* [↑] add if stem value is numeric.*/
end /*j*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
sayNodes: w= 9; do j=0 to nodes; _= /*ensure each of the nodes gets shown. */
do k=1 for stems; _= _ center(root.j.k, w) /*concatenate a node.*/
end /*k*/
$= word('node='j, 1 + (j<1) ) /*define a label for this line's output*/
say center($, w) substr(_, 2) /*ignore 1st (leading) blank which was */
end /*j*/ /* [↑] caused by concatenation.*/
say /*show a blank line to separate outputs*/
return
- output when using the default input:
═════════ ═════════ ═════════ node=1 1.00 1.00 1.00 node=2 1.10 1.10 1.10 node=3 1.11 1.11 1.11 node=4 1.12 1.12 1.12 node=5 1.20 1.20 1.20 node=6 1.21 1.21 1.21 node=7 1.22 1.22 1.22 ═════════ ═════════ ═════════ node=1 51.00 51.00 51.00 node=2 51.10 51.10 51.10 node=3 51.11 51.11 51.11 node=4 51.12 51.12 51.12 node=5 51.20 51.20 51.20 node=6 51.21 51.21 51.21 node=7 51.22 51.22 51.22
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<U> 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) });
}
Scala
There's much to be said about parametric polymorphism in Scala. Let's first see the example in question:
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)))
}
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:
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
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:
def toName(e: Employee) = e.name
val treeOfNames = t.map(toName)
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:
trait Function1[-T1, +R]
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:
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)
}
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:
if (t2.find(new Employee("Dilbert")))
println("Call Catbert!")
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:
trait DFA {
type Element
val map = new collection.mutable.HashMap[Element, DFA]()
}
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)
$ 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;
Output:
2 3 5 7 11 13 17 19 23
Standard ML
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)
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)
}
}
Another version based on Algebraic Data Types:
enum Tree<T> {
case Empty
indirect case Node(T, Tree<T>, Tree<T>)
func map<U>(f : T -> U) -> Tree<U> {
switch(self) {
case .Empty : return .Empty
case let .Node(x, l, r): return .Node(f(x), l.map(f), r.map(f))
}
}
}
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,
binary_tree_of "node-type" = "node-type"%hhhhWZAZ
or by way of a recurrence solved using a fixed point combinator imported from a library as shown below.
#import tag
#fix general_type_fixer 1
binary_tree_of "node-type" = ("node-type",(binary_tree_of "node-type")%Z)%drWZwlwAZ
(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.
binary_tree_of = %-hhhhWZAZ
A mapping combinator over this type can be defined with pattern matching like this
binary_tree_map "f" = ~&a^& ^A/"f"@an ~&amPfamPWB
or in point free form like this.
binary_tree_map = ~&a^&+ ^A\~&amPfamPWB+ @an
Here is a test program defining a type of binary trees of strings, and a function that concatenates each node with itself.
string_tree = binary_tree_of %s
x = 'foo': ('bar': (),'baz': ())
#cast string_tree
example = (binary_tree_map "s". "s"--"s") x
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 Basic .NET
Class BinaryTree(Of T)
ReadOnly Property Left As BinaryTree(Of T)
ReadOnly Property Right As BinaryTree(Of T)
ReadOnly Property Value As T
Sub New(value As T, Optional left As BinaryTree(Of T) = Nothing, Optional right As BinaryTree(Of T) = Nothing)
Me.Value = value
Me.Left = left
Me.Right = right
End Sub
Function Map(Of U)(f As Func(Of T, U)) As BinaryTree(Of U)
Return New BinaryTree(Of U)(f(Me.Value), Me.Left?.Map(f), Me.Right?.Map(f))
End Function
Overrides Function ToString() As String
Dim sb As New Text.StringBuilder()
Me.ToString(sb, 0)
Return sb.ToString()
End Function
Private Overloads Sub ToString(sb As Text.StringBuilder, depth As Integer)
sb.Append(New String(ChrW(AscW(vbTab)), depth))
sb.AppendLine(Me.Value?.ToString())
Me.Left?.ToString(sb, depth + 1)
Me.Right?.ToString(sb, depth + 1)
End Sub
End Class
Module Program
Sub Main()
Dim b As New BinaryTree(Of Integer)(6, New BinaryTree(Of Integer)(5), New BinaryTree(Of Integer)(7))
Dim b2 As BinaryTree(Of Double) = b.Map(Function(x) x * 0.5)
Console.WriteLine(b)
Console.WriteLine(b2)
End Sub
End Module
- Output:
6 5 7 3 2.5 3.5
Visual 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().
Wren
Wren is dynamically type and so doesn't have parametric polymorphism (PP) as such; in a sense every method or function is polymorphic over its parameters.
However, that doesn't mean that type safety is unimportant and, in the case of a Binary Tree, we'd generally want all its nodes to contain values of the same type.
Fortunately, we can simulate PP by passing an extra parameter to a collection class's contructor to specify the type of values to be used for that particular instantiation. We can then use this to guard against the wrong type of values being passed to the class's other methods.
class BinaryTree {
construct new(T, value) {
if (!(T is Class)) Fiber.abort ("T must be a class.")
if (value.type != T) Fiber.abort("Value must be of type T.")
_kind = T
_value = value
_left = null
_right = null
}
// constructor overload to enable kind to be inferred from type of value
static new (value) { new(value.type, value) }
kind { _kind }
value { _value}
value=(v) {
if (v.type != _kind) Fiber.abort("Value must be of type %(_kind)")
_value = v
}
left { _left }
right { _right }
left=(b) {
if (b.type != BinaryTree || b.kind != _kind) {
Fiber.abort("Argument must be a BinaryTree of type %(_kind)")
}
_left = b
}
right=(b) {
if (b.type != BinaryTree || b.kind != _kind) {
Fiber.abort("Argument must be a BinaryTree of type %(_kind)")
}
_right = b
}
map(f) {
var tree = BinaryTree.new(f.call(_value))
if (_left) tree.left = left.map(f)
if (_right) tree.right = right.map(f)
return tree
}
showTopThree() { "(%(left.value), %(value), %(right.value))" }
}
var b = BinaryTree.new(6)
b.left = BinaryTree.new(5)
b.right = BinaryTree.new(7)
System.print(b.showTopThree())
var b2 = b.map{ |i| i * 10 }
System.print(b2.showTopThree())
b2.value = "six" // generates an error because "six" is not a Num
- Output:
(5, 6, 7) (50, 60, 70) Value must be of type Num [./parametric_polymorphism line 17] in value=(_) [./parametric_polymorphism line 53] in (script)
- Programming Tasks
- Basic language learning
- Type System
- Ada
- C
- C sharp
- C++
- C3
- Ceylon
- Clean
- Clojure/Omit
- COBOL
- Common Lisp
- D
- Dart
- E
- FreeBASIC
- F Sharp
- Fortran
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Inform 7
- J
- Java
- Julia
- Kotlin
- Mathematica
- Wolfram Language
- Mercury
- Nim
- Objective-C
- OCaml
- Oforth/Omit
- PascalABC.NET
- Phix
- PicoLisp
- Prolog
- Racket
- Raku
- REXX
- Rust
- Scala
- Seed7
- Standard ML
- Swift
- Ursala
- Visual Basic .NET
- Visual Prolog
- Wren
- Axe/Omit
- Bc/Omit
- C/Omit
- Dc/Omit
- Factor/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
- VBA/Omit
- Zkl/Omit