74

I read Wikipedia's explanation of idempotence. I know it means a function's output is determined by it's input. But I remember that I heard a very similar concept: pure function. I Google them but can't find their difference...

Are they equivalent?

Richard JP Le Guen
  • 28,364
  • 7
  • 89
  • 119
Lai Yu-Hsuan
  • 27,509
  • 28
  • 97
  • 164
  • 2
    it may be useful for someone looking to understand the concept: http://pedrorijo.com/blog/fp-concepts/ – pedrorijo91 Feb 24 '17 at 11:10
  • According to [this excellent answer with examples](https://stackoverflow.com/a/9561780/1498178) (paraphrasing): For **functions WITHOUT side effects** (**pure functions**), idempotency implies that f(x) = f(f(x)) = f(f(f(x))) = f(f(f(f(x)))) = ...... for all values of x. For **functions WITH side effects**, idempotency furthermore implies that no additional side effects will be caused after the first application. You can consider the state of the world to be an additional "hidden" parameter to the function if you like. – toraritte Aug 04 '22 at 05:21
  • But then there is this conclusion from [Is a pure function idempotent?](https://stackoverflow.com/questions/33010633/is-a-pure-function-idempotent): "_Only if the pure function returns f(f(x)) === f(x), which is the case only if the function returns nothing. A good example given is double(x), and it's kinda obvious double(double(x)) !== double(x)_" – toraritte Aug 04 '22 at 05:32

6 Answers6

77

An idempotent function can cause idempotent side-effects.

A pure function cannot.

For example, a function which sets the text of a textbox is idempotent (because multiple calls will display the same text), but not pure.
Similarly, deleting a record by GUID (not by count) is idempotent, because the row stays deleted after subsequent calls. (additional calls do nothing)

SLaks
  • 868,454
  • 176
  • 1,908
  • 1,964
  • Example of idempotent side-effect? Is that something like printing to stdout? – Rafe Kettler Jan 26 '11 at 03:58
  • @Rafe: Changing a database. For example, changing a field in a record. – Robert Harvey Jan 26 '11 at 03:59
  • 1
    @Rafe: Printing to stdout isn't idempotent because each call prints another line. – SLaks Jan 26 '11 at 04:00
  • IMO, deleting a record's side-effect is not idempotent. You can't delete it twice. – leppie Jan 26 '11 at 04:06
  • 1
    @leppie: But after calling the function twice, nothing changes. Thus, it **is** idempotent. For example, HTTP's `DELETE` verb. – SLaks Jan 26 '11 at 04:10
  • 5
    Deletion is idempotent as long as no error is encountered on failure to delete - the state of the world after one application is the same as after 2 - the row has been deleted - and as long as the state of the world and the result are the same after n>=1 calls as after 1 call, it is, by definition, idempotent. If however it complains then it isn't e.g. if it prints to stderr on error. – tobyodavies Jan 26 '11 at 07:33
23

A pure function is a function without side-effects where the output is solely determined by the input - that is, calling f(x) will give the same result no matter how many times you call it.

An idempotent function is one that can be applied multiple times without changing the result - that is, f(f(x)) is the same as f(x).

A function can be pure, idempotent, both, or neither.

Anon.
  • 58,739
  • 8
  • 81
  • 86
  • 11
    But a pure function _must_ be idempotent. – SLaks Jan 26 '11 at 13:47
  • I guess your explanation is "mathematical" idempotent function. It's different from computing field. – Lai Yu-Hsuan Jan 26 '11 at 14:24
  • 3
    @user590083: No, his explanation is valid in the computing field. However, changed computing state is part of the output, in the context of Anon's answer. – Brian Jan 26 '11 at 17:50
  • 21
    @SLaks: Not true. `f(x) = x+1` isn't idempotent, since `f(f(1)) != f(1)`. – porges Oct 14 '11 at 02:43
  • @Porges, of course `f(2) != f(1)`. What does that have to do with idempotency? Just because a function for which `f(f(x)) == f(x)` is true is also idempotent, does not mean all idempotent functions must have that property. So `f(x) = x+1` is pure, hence idempotent. – nilskp Jun 20 '13 at 20:47
  • 1
    @nilskp Purity is a distinct concept from idempotence; you seem to be misunderstanding its definition. Idempotence means additional successive compositions of the operation or function (on the output of the first function application) will not give a different output, i.e., f(x) = f(f(x)) = f(f(f(x))) = ... etc. Purity means that the same input (NOT the output of any previous application) will give the same output, regardless of time or the state of the external world. – dxuhuang Nov 19 '14 at 17:23
  • 1
    @dxh, I'm well aware of both definitions, so either I wrote something that's being misinterpreted, or you read it wrong. – nilskp Nov 19 '14 at 18:19
  • 1
    @nilskp forgive me if I did misinterpret, but you seemed to imply that 1) purity implies idempotence 2) and idempotence is NOT the same as f(f(x)) == f(x). Both of these are wrong. – dxuhuang Nov 19 '14 at 21:22
  • @dxh, I'll admit that I never understood the `f(f(x)) == f(x)` property. Perhaps it's not meant to be understood literally, but the way I read it, it seems to imply that idempotent functions must have the same output type as input type, otherwise one would not be able to pass the output as input. Can you clarify this? – nilskp Nov 20 '14 at 14:33
  • @nilskp yes, this property is meant to be understood in the context of mathematics (and functional programming languages). the input and output are indeed of the same type, or else successive applications would not make sense. – dxuhuang Nov 20 '14 at 18:59
  • 2
    @nilskp in imperative programming languages, a statement consisting of a call to f(x) is an invocation of a hypothetical function (not f) that takes as input the "state of the world" and outputs a different state when the call returns. If further calls to f(x) after the first one don't change anything, then f(x) can be called idempotent as well. – dxuhuang Nov 20 '14 at 19:07
10

No, an idempotent function will change program/object/machine state - and will make that change only once (despite repeated calls). A pure function changes nothing, and continues to provide a (return) result each time it is called.

Brent Arias
  • 29,277
  • 40
  • 133
  • 234
6

Functional purity means that there are no side effects. On the other hand, idempotence means that a function is invariant with respect to multiple calls.

Every pure function is side effect idempotent because pure functions never produce side effects even if they are called more then once. However, return value idempotence means that f(f(x)) = f(x) which is not effected by purity.

jhuni
  • 425
  • 3
  • 4
4

A large source of confusion is that in computer science, there seems to be different definitions for idempotence in imperative and functional programming.

From wikipedia (https://en.wikipedia.org/wiki/Idempotence#Computer_science_meaning)

In computer science, the term idempotent is used more comprehensively to describe an operation that will produce the same results if executed once or multiple times. This may have a different meaning depending on the context in which it is applied. In the case of methods or subroutine calls with side effects, for instance, it means that the modified state remains the same after the first call. In functional programming, though, an idempotent function is one that has the property f(f(x)) = f(x) for any value x.

Since a pure function does not produce side effects, i am of the opinion that idempotence has nothing to do with purity.

lohfu
  • 601
  • 5
  • 10
0

I've found more places where 'idempotent' is defined as f(f(x)) = f(x) but I really don't believe that's accurate. Instead I think this definition is more accurate (but not totally):

describing an action which, when performed multiple times on the same subject, has no further effect on its subject after the first time it is performed. A projection operator is idempotent.

The way I interpret this, if we apply f on x (the subject) twice like:

f(x);f(x);

then the (side-)effect is the same as

f(x);

Because pure functions dont allow side-effects then pure functions are trivially also 'idempotent'.

A more general (and more accurate) definition of idempotent also includes functions like

toggle(x)

We can say the degree of idempotency of a toggle is 2, because after applying toggle every 2 times we always end up with the same State

Ibrahim ben Salah
  • 742
  • 3
  • 15