Hacker News Reader

Comment by Hexstream | Hacker News Reader

"A function is "idempotent" if the result of doing it twice (feeding the output of the first call into the second call) is exactly the same as the result of doing it once. (Or, in other words, every output of the function is idempotent under it.)"

Uh?? According to this definition this wouldn't be idempotent:

  (defun add-one (x)
    (+ x 1))

  CL-USER> (values (add-one 5)
           (add-one (add-one 5))
           (= (add-one 5) (add-one (add-one 5))))
  6
  7
  nil

edit: What the... Wikipedia seems to be agreeing with him. It seems I mixed up idempotence and referential transparency, I thought they were equivalent concepts. I'm confused...

View on HN

The concepts of referential transparency and idempotence are close, but not quite equivalent.

'Idempotence' is the property that you can run something 1 or 100 times, and there is no difference in post-conditions. "x=1" is an idempotent operation. Idempotent operations can have side-effects.

'Referential transparency' means you can replace an expression with the value it returns, and it makes no difference in post-conditions. The expression "x=1", while idempotent, is not referentially transparent; the expression (in most languages) will return a value of 1, but you cannot replace "x=1" with "1" in your code and expect the same post-conditions. Referentially-transparent expressions cannot have side-effects.

His definition of idempotence is correct. As an example, a hash table with idempotent delete would work fine if I did this:

  (setf h (hash-new))
  (hash-insert h 'foo '(1 2 3 4))
  (hash-delete h 'foo)
  ;;; some time later
  (hash-delete h 'foo)

A non-idempotent implementation might complain that 'foo doesn't exist in the table.

I think Jeff conveys the wrong sense of idempotence. He has somehow extracted the purely mathematical sense, while the source he quotes goes on to explain the programming angle.

Yeah, I had never heard 'idempotence' used in a mathematical sense before. I just think of that as a function hitting a fixed point.

I think it's much more common to talk about idempotence in programming w.r.t. state and state transitions. With immutable data, this approaches the mathematical definition:

    (= (remove-el set 1) (remove-el (remove-el set 1) 1))

With network protocols, state machines, and mutable data, idempotence helps ensure consistent state without the fixed-point-ness.

A good example of an idempotent function is the absolute value function.

abs(-1) = abs(abs(-1) since both equal 1

Reply on news.ycombinator.com