Idempotence is an essential tool in programming. It has many uses, from improving fault tolerance, clarifying code, to writing declarative deployment scripts. It’s important to understand what idempotent means. There are a lot of unclear, and often incorrect, definitions floating around.
The functional unary operation
In it’s simplest form, an idempotent function has this property:
1 |
op( op(x) ) == op(x) |
If you pass the output from the first call to the second you end up with the same result. You can continue with this chain as long as you want and still not change the result: op( op( op( op( x ) ) ) ) == op(x).
A good example of an idempotent function is uppercase for a string.
1 2 |
uppercase( 'Hello' ) == 'HELLO' uppercase( uppercase( 'Hello' ) ) == 'HELLO' |
lowercase is also an idempotent function, as is truncate. For math operations abs is the standard example, also common are floor, ceil, and mod.
There is also a definition of idempotence for binary functions, and something called the idempotent element. These are not as interesting from a programming viewpoint so I’m leaving them out of this article.
Stateful idempotence
The functional definition works well with functions that don’t have side-effects. It’s hard to see how it directly correlates to imperative programming, so we call the following property idempotent as well:
1 2 3 4 5 |
type a a.op() type temp = clone(a) a.op() temp == a |
We can call a.op as many times as we’d like and the result will be the same. It’s a stateful idempotence that is quite common in programming.
This stateful definition actually derives from the pure one. I’ll explain this at the end of the article.
A common stateful idempotent function is sorting a collection:
1 2 3 |
a = [ 8 4 7 2 ] a.sort() // a == [ 2 4 7 8 ] a.sort() // a == [ 2 4 7 8 ] |
Parameterized idempotence
We also allow that some non-unary functions can be idempotent. For example, removing by value from a list is idempotent so long as you keep passing the same value:
1 2 3 |
a = [ 8 4 7 2 ] a.remove( 4 ) // a == [ 8 7 2 ] a.remove( 4 ) // a == [ 8 7 2 ] |
HTTP PUT is also called idempotent in this same sense. If you issue multiple PUT requests with the same parameters the result is the same. It’s good for fault tolerance as you can keep reissuing the PUT request until you’re positive it works.
HTTP DELETE, or file deletion, is also considered idempotent. The result is the resource no longer exists. If called again the success code may differ, but the resource will still not exist. In fault tolerant systems we often prefer to mark the success of an operation based on the result, in which case deleting a non-extant resource would be successful. I can return to this topic in a later article.
It’s still just unary
The stateful and parameterized idempotence are really just unary idempotence in disguise. They follow the same definition we gave at the beginning:
1 |
op( op(x) ) == op(x) |
The trick is to look at them from a functional view, transforming them a little. The stateful case is actually quite easy. Any stateful operation like a.op() can instead be expressed as a = op(a). op is a unary function on a. The list sorting example can be expressed this way:
1 2 3 |
a = [ 8 4 7 2 ] a = sort(a) // a == [ 2 4 7 8 ] a = sort(a) // a == [ 2 4 7 8 ] |
The parameterized idempotence can also be reduced to the unary form. Anybody familiar with composition, closures, or lambda functions can see this. Let’s rewrite the remove example in this fashion:
1 2 3 4 5 6 7 |
op = ( list ) -> { return remove( list, 4 ) } a = [ 8 4 7 2 ] a = op(a) // a == [ 8 7 2 ] a = op(a) // a == [ 8 7 2 ] |
As long as the operation combined with the parameters can be expressed in this unary form we can rely on the same definition of idempotence.
