86

I read Wikipedia's explanation of idempotence. I know it means a function's output is determined by its 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?

Improve this question
3
  • 2
    it may be useful for someone looking to understand the concept: pedrorijo.com/blog/fp-concepts Commented Feb 24, 2017 at 11:10
  • 1
    According to this excellent answer with examples (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. Commented Aug 4, 2022 at 5:21
  • But then there is this conclusion from 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)" Commented Aug 4, 2022 at 5:32

8 Answers 8

Reset to default
90

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)

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Example of idempotent side-effect? Is that something like printing to stdout?
@Rafe: Changing a database. For example, changing a field in a record.
@Rafe: Printing to stdout isn't idempotent because each call prints another line.
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.
29

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.

Improve this answer

Comments

12

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.

Improve this answer

Comments

10

Definitions:

  • Pure: f(x) always returns the same value for a given x.
  • Idempotent: f(f(x)) = f(x).

Examples

Not pure, and not idempotent

def f(x): return random()

Check:

f(0) = 0.2171 f(0) = 0.3142 # Thus, impure.

Pure, but not idempotent

def f(x): return x + 1

Check:

f(0) = 1 f(0) = 1 # Thus, pure. f(1) = 2 # Thus, not idempotent since f(0) != f(f(0)).

Pure, and idempotent

def f(x): return round(x)

Check:

f(0.3142) = 0 f(0.3142) = 0 # Thus, pure. f(0) = 0 # Thus, idempotent.

Visualization

graph diagrams

Each arrow denotes an application of f.

Notice that the idempotent graph ends up in a 1-cycle after one application of f.

What about "not pure, but idempotent"?

Impossible. Proof by contradiction:

Assume f is impure and idempotent. Impure f implies there exists x such that if f(x) = a and f(x) = b, then it is possible that a != b. Say that happens. Now, by idempotency, f(a) = a and f(b) = b. But then:

a = f(a) = f(f(x)) = f(b) = b

...so, a = b. We have reached a contradiction. Clearly, f cannot be simultaneously impure and idempotent!

Improve this answer

3 Comments

Amazing answer!
This would imply that an idempotent function must have the same input argument as its return value. abs() is a simple example where that's true. But what about a void function that deletes a database record and produces no other side effects? It seems there are multiple definitions in use, even within this SO post. Is there a more specific distinction between the two meanings?
@Keavon Consider delete_bobs(delete_bobs(db)) = delete_bobs(db). It is imprecise to say that delete_records is idempotent. It's not idempotent on its own. But delete_bobs = lambda db: delete_records(db, "name", "bob") is idempotent. In fact, the same holds true for all key-value pairs, so generally, all functions of the form lambda db: delete_records(db, •, •) are idempotent. Note that we are assuming db is some immutable object. delete_records returns a modified copy of the inputted db.
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.

Improve this answer

Comments

6

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.

Improve this answer

Comments

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

Improve this answer

2 Comments

Actually, f(x) = f(f(x)) is certainly a rigorous and accurate definition of idempotency. In your example with "f(x); f(x); having the same side-effects as f(x)" being a showcase of "idempotency", the idempotent function is not f... it is a hidden function called call_f_x that acts on real-world state. Then, call_f_x(call_f_x(state)) = call_f_x(state). Which is indeed the exact definition of an idempotent function.
...P.S. This explicit formulation of the impure state is similar to how Haskell forces programmers to model side-effects in pure functions. call_f_x is pure, despite the "side-effects" that happen to state.
0

As others have said, the word "idempotent" has multiple distinct meanings.

In a pure-functional context, idempotent means f(f(x)) == f(x). But in an impure context, this bifurcates into two different conditions, due to the fact that f(f(x)) == f(x) may evaluate to True for all x values, despite that the overall effect of f(f(x)) may be different to the overall effect of f(x), making f(x) and f(f(x)) non-interchangeable from a compilation perspective.

To add insult to injury, idempotent can also mean side_effect[f(x); f(x)] == side_effect[f(x)]. Furthermore, if this condition is satisfied, then the definitional bifurcation described in the previous paragraph doesn't occur. Note that f is pure if and only if side_effect[f(x)] == side_effect[]. From this we see that a pure function is automatically idempotent in the final sense of the word.

Improve this answer

2 Comments

As I argue for here, I think the "side-effect" definition is just a special case of the original definition g(g(x)) == g(x). Let f :: (RealWorld, a) -> b, where g = partial(f, real_world_state). Then, there are functions f such that g is idempotent. The only difference is that people (incorrectly) say f is idempotent, when in actuality, partial(f, real_world_state) is the idempotent function that they are referring to.
Basically, you're associating with each impure function $f : X \rightarrow Y$ an associated pure function $f^* : \mathrm{State} \times X \rightarrow Y$, and observing that $\mathrm{StronglyIdempotent}(f)$ is equivalent to $\forall s \in \mathrm{S} : \mathrm{Idempotent}(x \mapsto f(s,x)).$ It's a good viewpoint, but doesn't really undermine what I'm saying here. You can look up terms like "heteromorphism" and "profunctor" and "Kleisli category" to learn more about why the impure viewpoint is also valid, and complementary to the pure viewpoint.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.