Mere Code

Diverse Topics of General Interest to the Practicing Programmer

Trips me every time

etrepum commented on how hash functions need to be idempotent. I pretty much always interpret things about functions and idempotence incorrectly.

When used in computing, saying a function is idempotent generally means you can call it a hozillion times and the state of the system (& thus the return value of the function) will be the same as if you called it once.

When used in mathematics, a function f is idempotent if f(f(x)) = f(x) for all x. The computing quality of idempotence isn’t useful since f(x) = f(x).

I would greatly appreciate it if we could all find a way to communicate that didn’t involve language.


ddaa on 2009-03-25 23:23
Michael Hudson: Oh right! I remember now.

Actually, idempotency in the computing sense is only meaningful where there ARE side effects.

For a couple of pythonic examples: “a[b] = c” where a is a list IS idempotent. But “a.pop()” is not.

Since the last thing you want from a hash function is to mutate its argument, the only meaningful sense for “idempotent hash function” is the mathematical one.

And etrepum is confused.
Michael Hudson on 2009-03-25 22:08
Idempotency (in computing) is not the same as side-effect free, or always returning the same value for the same arguments, but rather than calling it multiple times has the same effect as calling it once. Bob is perhaps using bigs words where simple ones would do :)

Alex is right that this is the same as the mathematical definition if you view the state of the world as implicitly passed to and returned from every function you call.
larstiq on 2009-03-25 20:36
Oh feh, I had to reread your quote of Bob and then his original post before I got it not being what I thought it was.

I do use idempotent in computing in the mathy way, but maybe that is because I’m a math student.
Alex on 2009-03-25 16:14
The mathematics definition of idempotent sort of makes sense in computing if you view a function as taking a state and returning the state of the system after the function is applied.

Then the property f(f(x)) = f(x) seems like a desirable one if equality is replaced by some equivalence relation

This is still weaker than invariance of f though…
ddaa on 2009-03-25 12:07
Oh, a new pet peeve!

From now on I’ll make it a point that “idempotent” DOES mean “f(f(x)) = f(x)”.

I did not realize that people were using it with this other, incorrect meaning.

f(x)=f(x) is invariant, or referentially transparent, or side-effect free, whatever. Real idempotence is a useful property to be able to name in computing.

Join me and embrace the joy of self-righteousness!
jml on 2009-03-25 07:19

I guess my point is that the clarity of the terms depends on the domain that you are speaking in.
Eric on 2009-03-25 07:16
You could just say that the function need be referentially transparent.