What is the difference between an Idempotent and a Deterministic function?

Question

Are they both (idempotent functions and deterministic functions) just functions that return the same result given the same inputs?

Or is there a distinction that I'm missing? (And if there is a distinction, could you please help me understand what it is)

Answer 1

In more simple terms:

• Pure deterministic function: The output is based entirely, and only, on the input values and nothing else: there is no other (hidden) input or state that it relies on to generate its output. There are no side-effects or other output.
• Impure deterministic function: As with a deterministic function that is a pure function: the output is based entirely, and only, on the input values and nothing else: there is no other (hidden) input or state that it relies on to generate its output - however there is other output (side-effects).
• Idempotency: The practical definition is that you can safely call the same function multiple times without fear of negative side-effects. More formally: there are no changes of state between subsequent identical calls.

Idempotency does not imply determinacy (as a function can alter state on the first call while being idempotent on subsequent calls), but all pure deterministic functions are inherently idempotent (as there is no internal state to persist between calls). Impure deterministic functions are not necessarily idempotent.

	Pure deterministic	Impure deterministic	Pure Nondeterministic	Impure Nondeterministic	Idempotent
Input	Only parameter arguments (incl. this)	Only parameter arguments (incl. this)	Parameter arguments and hidden state	Parameter arguments and hidden state	Any
Output	Only return value	Return value or side-effects	Only return value	Return value or side-effects	Any
Side-effects	None	Yes	None	Yes	After 1st call: Maybe. After 2nd call: None
SQL Example	UCASE	CREATE TABLE	GETDATE		DROP TABLE
C# Example	String.IndexOf	List<T>.Add	DateTime.Now	Random.Next	Directory.Create[1]

• [1] - Directory.Create is idempotent because if the directory already exists then it returns a new DirectoryInfo instance as though it did just create a new filesystem directory (just like CreateFile can be used to open an existing file).

Determinacy of Pure Functions

For example, in SQL UCASE(val), or in C#/.NET String.IndexOf are both deterministic because the output depends only on the input. Note that in instance methods (such as IndexOf) the instance object (i.e. the hidden this parameter) counts as input, even though it's "hidden":

"foo".IndexOf("o") == 1 // first cal "foo".IndexOf("o") == 1 // second call // the third call will also be == 1 

Whereas in SQL NOW() or in C#/.NET DateTime.UtcNow is not deterministic because the output changes even though the input remains the same (note that property getters in .NET are equivalent to a method that accepts no parameters besides the implicit this parameter):

 DateTime.UtcNow == 2016-10-27 18:10:01 // first call  DateTime.UtcNow == 2016-10-27 18:10:02 // second call 

Idempotency

A good example in .NET is the Dispose() method: See Should IDisposable.Dispose() implementations be idempotent?

a Dispose method should be callable multiple times without throwing an exception.

So if a parent component X makes an initial call to foo.Dispose() then it will invoke the disposal operation and X can now consider foo to be disposed. Execution/control then passes to another component Y which also then tries to dispose of foo, after Y calls foo.Dispose() it too can expect foo to be disposed (which it is), even though X already disposed it. This means Y does not need to check to see if foo is already disposed, saving the developer time - and also eliminating bugs where calling Dispose a second time might throw an exception, for example.

Another (general) example is in REST: the RFC for HTTP1.1 states that GET, HEAD, PUT, and DELETE are idempotent, but POST is not ( https://www.w3.org/Protocols/rfc2616/rfc2616-sec9.html )

Methods can also have the property of "idempotence" in that (aside from error or expiration issues) the side-effects of N > 0 identical requests is the same as for a single request. The methods GET, HEAD, PUT and DELETE share this property. Also, the methods OPTIONS and TRACE SHOULD NOT have side effects, and so are inherently idempotent.

So if you use DELETE then:

Client->Server: DELETE /foo/bar // `foo/bar` is now deleted Server->Client: 200 OK Client->Server DELETE /foo/bar // foo/bar` is already deleted, so there's nothing to do, but inform the client that foo/bar doesn't exist Server->Client: 404 Not Found // the client asks again: Client->Server: DELETE /foo/bar // foo/bar` is already deleted, so there's nothing to do, but inform the client that foo/bar doesn't exist Server->Client: 404 Not Found 

So you see in the above example that DELETE is idempotent in that the state of the server did not change between the last two DELETE requests, but it is not deterministic because the server returned 200 for the first request but 404 for the second request.

Answer 2

A deterministic function is just a function in the mathematical sense. Given the same input, you always get the same output. On the other hand, an idempotent function is a function which satisfies the identity

f(f(x)) = f(x)  

As a simple example. If UCase() is a function that converts a string to an upper case string, then clearly UCase(Ucase(s)) = UCase(s).

Idempotent functions are a subset of all functions.