Idempotence

Uses your system voice; voice and rate in settings.

Snapshot

≈ 8 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

control panel. Pressing the On button (green) is an idempotent operation, since it has the same effect whether done once or multiple times. Likewise, pressing Off is idempotent. Idempotence ( , ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of places in abstract algebra (in particular, in the theory of projectors and closure operators) and functional programming (in which it is connected to the property of referential transparency). The term was introduced by American mathematician Benjamin Peirce in 1870 in the context of elements of algebras that remain invariant when raised to a positive integer power, and literally means "(the quality of having) the same power", from + potence (same + power).

control panel. Pressing the On button (green) is an idempotent operation, since it has the same effect whether done once or multiple times. Likewise, pressing Off is idempotent. Idempotence ( , ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application.

The concept of idempotence arises in a number of places in abstract algebra (in particular, in the theory of projectors and closure operators) and functional programming (in which it is connected to the property of referential transparency).

The term was introduced by American mathematician Benjamin Peirce in 1870 in the context of elements of algebras that remain invariant when raised to a positive integer power, and literally means "(the quality of having) the same power", from + potence (same + power). x\cdot x=x The binary operation \cdot is said to be idempotent if x\cdot x=x \text{ for all } x\in S In a group (G, \cdot) , the identity element e is the only idempotent element.

Indeed, if x is an element of G such that , then and finally x=e by multiplying on the left by the inverse element of x . In the monoids (\mathcal{P}(E), \cup) and (\mathcal{P}(E), \cap) of the power set \mathcal{P}(E) of the set E with set union \cup and set intersection \cap respectively, \cup and \cap are idempotent. Indeed, , and . In the monoids (\{0, 1\}, \vee) and (\{0, 1\}, \wedge) of the Boolean domain with logical disjunction \vee and logical conjunction \wedge respectively, \vee and \wedge are idempotent. Indeed, , and .

In a GCD domain (for instance in \mathbb{Z} ), the operations of GCD and LCM are idempotent. In a Boolean ring, multiplication is idempotent. In a tropical semiring, addition is idempotent. In a ring of quadratic matrices, the determinant of an idempotent matrix is either 0 or 1. If the determinant is 1, the matrix necessarily is the identity matrix.

Idempotent functions

In the monoid (E^E, \circ) of the functions from a set E to itself (see set exponentiation) with function composition \circ , idempotent elements are the functions such that , that is such that (in other words, the image f(x) of each element x\in E is a fixed point of f ). For example: the absolute value is idempotent.

Indeed, , that is ; constant functions are idempotent; the identity function is idempotent; the floor, ceiling and fractional part functions are idempotent; the real part function \mathrm{Re}(z) of a complex number, is idempotent. for most kinds of average, taking the average of a set and putting it in a singleton set is idempotent: \{\operatorname{avg}\{\operatorname{avg}\{x_1,\dots,x_n\}\}\} = \{\operatorname{avg}\{x_1,\dots,x_n\}\} the subgroup generated function from the power set of a group to itself is idempotent; the convex hull function from the power set of an affine space over the reals to itself is idempotent; the closure and interior functions of the power set of a topological space to itself are idempotent; the Kleene star and Kleene plus functions of the power set of a monoid to itself are idempotent; the idempotent endomorphisms of a vector space are its projections.

If the set E has n elements, we can partition it into k chosen fixed points and non-fixed points under f , and then k^{n-k} is the number of different idempotent functions. Hence, taking into account all possible partitions, \sum_{k=0}^n {n \choose k} k^{n-k} is the total number of possible idempotent functions on the set. The integer sequence of the number of idempotent functions as given by the sum above for n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... starts with 1, 1, 3, 10, 41, 196, 1057, 6322, 41393, ... .

Neither idempotence nor non-idempotence is preserved under function composition. As an example for the former, mod 3 and g(x)=\max(x, 5) are both idempotent, but is not, although happens to be. As an example for the latter, the negation function \neg on the Boolean domain is not idempotent, but is. Similarly, unary negation of real numbers is not idempotent, but is. In both cases, the composition is simply the identity function, which is idempotent.

Idempotent morphisms

A morphism f : x \to x in a category is called idempotent if f \circ f = f . An idempotent is said to split if it can be written as f = h \circ g for some g : x \to y, \, h : y \to x with g \circ h = \operatorname{id} . A category is said to be idempotent complete if every idempotent splits.

For example, \mathsf{Set} is idempotent complete. int x = 3; void inspect() { printf("%d\n", x); } void change() { x = 5; } void sequence() { inspect(); change(); inspect(); } int main() { sequence(); // prints "3\n5\n" sequence(); // prints "5\n5\n" return 0; } In the Hypertext Transfer Protocol (HTTP), idempotence and safety are the major attributes that separate HTTP methods. Of the major HTTP methods, GET, PUT, and DELETE should be implemented in an idempotent manner according to the standard, but POST doesn't need to be.

GET retrieves the state of a resource; PUT updates the state of a resource; and DELETE deletes a resource. As in the example above, reading data usually has no side effects, so it is idempotent (in fact nullipotent). Updating and deleting a given data are each usually idempotent as long as the request uniquely identifies the resource and only that resource again in the future.

PUT and DELETE with unique identifiers reduce to the simple case of assignment to a variable of either a value or the null-value, respectively, and are idempotent for the same reason; the end result is always the same as the result of the initial execution, even if the response differs. Violation of the unique identification requirement in storage or deletion typically causes violation of idempotence.

For example, storing or deleting a given set of content without specifying a unique identifier: POST requests, which do not need to be idempotent, often do not contain unique identifiers, so the creation of the identifier is delegated to the receiving system which then creates a corresponding new record. Similarly, PUT and DELETE requests with nonspecific criteria may result in different outcomes depending on the state of the system – for example, a request to delete the most recent record.

In each case, subsequent executions will further modify the state of the system, so they are not idempotent. In event stream processing, idempotence refers to the ability of a system to produce the same outcome, even if the same file, event or message is received more than once. In a load–store architecture, instructions that might possibly cause a page fault are idempotent. So if a page fault occurs, the operating system can load the page from disk and then simply re-execute the faulted instruction.

In a processor where such instructions are not idempotent, dealing with page faults is much more complex. When reformatting output, pretty-printing is expected to be idempotent. In other words, if the output is already "pretty", there should be nothing to do for the pretty-printer. In service-oriented architecture (SOA), a multiple-step orchestration process composed entirely of idempotent steps can be replayed without side-effects if any part of that process fails.

Many operations that are idempotent often have ways to "resume" a process if it is interrupted ways that finish much faster than starting all over from the beginning. For example, resuming a file transfer, synchronizing files, creating a software build, installing an application and all of its dependencies with a package manager, etc.

External links

"idempotent" at the Free On-line Dictionary of Computing

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378034392 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

11 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.