Genericity: Difference between revisions
No edit summary |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 10: | Line 10: | ||
A '''comparison''' on a finite or infinite set <math>S</math> is a binary relation <math>c:S\times S \rightarrow \{ -1,0,+1\}</math> with the following properties: | A '''comparison''' on a finite or infinite set <math>S</math> is a binary relation <math>c:S\times S \rightarrow \{ -1,0,+1\}</math> with the following properties: | ||
* <math>c(x,x) = 0</math> for all <math>x \in S</math> (reflexivity), | * <math>c(x,x) = 0</math> for all <math>x \in S</math> (reflexivity), | ||
* <math>c(x,y)=-c(y,x)</math> for all <math>x,y \in S</math> (anti- | * <math>c(x,y)=-c(y,x)</math> for all <math>x,y \in S</math> (anti-symmetry), and | ||
* <math>(c(x,y) = 1 \land c(y,z) = 1) \Rightarrow c(x,z)=1</math> for all <math>x,y,z \in S</math> (transitivity) | * <math>(c(x,y) = 1 \land c(y,z) = 1) \Rightarrow c(x,z)=1</math> for all <math>x,y,z \in S</math> (transitivity). | ||
For convenience, we write <math>x<y</math> in case <math>c(x,y)=1</math>, <math>x\le y</math> in case <math>c(x,y)\ge 0</math>, and so on. | For convenience, we write <math>x<y</math> in case <math>c(x,y)=1</math>, <math>x\le y</math> in case <math>c(x,y)\ge 0</math>, and so on. | ||
===Remark=== | ===Remark=== | ||
Note that <math>c(x,y)=0</math> does '''not''' imply <math>x=y</math>. If <math>c(x,y)=0</math> actually implies <math>x=y</math> for all <math>x,y</math>, such a binary relation is usually called a '''total''' or '''linear order''' - as opposed to '''partial orders''', in which | Note that <math>c(x,y)=0</math> does '''not''' imply <math>x=y</math>. If <math>c(x,y)=0</math> actually implies <math>x=y</math> for all <math>x,y</math>, such a binary relation is usually called a '''total''' or '''linear order''' - as opposed to '''partial orders''', in which <math>c(x,y)=0</math> is possible for <math>x\neq y</math>. In the last case, we say <math>x</math> and <math>y</math> are '''incomparable'''. | ||
Latest revision as of 12:45, 21 May 2015
Definition
An algorithmic problem, algorithm, abstract data structure, or implementation of a data structure is generic if one or more related types are left open in the definition. The choice of these types is deferred until the algorithm is called or an object of the data structure is created.
Remark: Typically, there are requirements on the open types. This means an open type must offer some methods with prescribed syntax and semantics. Quite different concepts to formulate and ensure syntactical requirements are implemented in the various programming languages that support genericity.
Comparison
A comparison on a finite or infinite set [math]\displaystyle{ S }[/math] is a binary relation [math]\displaystyle{ c:S\times S \rightarrow \{ -1,0,+1\} }[/math] with the following properties:
- [math]\displaystyle{ c(x,x) = 0 }[/math] for all [math]\displaystyle{ x \in S }[/math] (reflexivity),
- [math]\displaystyle{ c(x,y)=-c(y,x) }[/math] for all [math]\displaystyle{ x,y \in S }[/math] (anti-symmetry), and
- [math]\displaystyle{ (c(x,y) = 1 \land c(y,z) = 1) \Rightarrow c(x,z)=1 }[/math] for all [math]\displaystyle{ x,y,z \in S }[/math] (transitivity).
For convenience, we write [math]\displaystyle{ x\lt y }[/math] in case [math]\displaystyle{ c(x,y)=1 }[/math], [math]\displaystyle{ x\le y }[/math] in case [math]\displaystyle{ c(x,y)\ge 0 }[/math], and so on.
Remark
Note that [math]\displaystyle{ c(x,y)=0 }[/math] does not imply [math]\displaystyle{ x=y }[/math]. If [math]\displaystyle{ c(x,y)=0 }[/math] actually implies [math]\displaystyle{ x=y }[/math] for all [math]\displaystyle{ x,y }[/math], such a binary relation is usually called a total or linear order - as opposed to partial orders, in which [math]\displaystyle{ c(x,y)=0 }[/math] is possible for [math]\displaystyle{ x\neq y }[/math]. In the last case, we say [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] are incomparable.