Hacker News Reader

Comment by o11c | Hacker News Reader

This fails to address that fundamental confusion, which is that there are several different (but related) things all called "idempotent":

1. a value `v` such that, for some pure binary function `f` (specified by context), `v === f(v, v)`

2. a pure binary function `g` such that, for all values `x`, `x === g(x, x)`

3. a pure unary function `h` such that, for all values `x`, `h(x) === h(h(x))`. Often this is formed as a partial evaluation of a binary function, as a relaxation of the previous kind.

4. a (non-pure) procedure that, when called with "the same" arguments (FSVO same), has no side-effects after the first time.

5. a binary relation `R` such that, for all values `x, z`, `R(x, z) <-> there exists some y such that R(x, y) AND R(y, z)`

(Edit: note before I clarified my variable names `v` used to be another `x`, and `g` and `h` both used to be another `f`)

View on HN

I've yet to encounter the second definition, and the first only when f is associative (otherwise f(x,x) = x doesn't seem strong enough).

All the others are just the many ways x^n can equal x (for all n>0) for various associative operators. Reusing 'f' for both the binary functions and the unary ones is needlessly misleading by the way, the unary f behaves more like x in the other examples.

And yes if you want R^2 = R then the condition only needs to hold for some y. It's related to transitivity.

You don't need associativity:

(x ⋅ x) ⋅ x

(x) ⋅ x

x ⋅ (x)

x ⋅ (x ⋅ x)

You do need (some subset of) associativity:

  (y0 * x) * x ?= y0 * (x * x)
        y1 * x ?= y0 * x
            y2 ?= y1

y2 is not in general constrained to be the same as y1 otherwise.

Good point about reusing variables, I've renamed all except the ones introduced locally.

I would only say that these are "isomorphic to" others; in the real world people do think of them differently, so it is important to enumerate them. And in particular people do think "the function", even though different the functions act differently.

(the real question is, did I ever see "left-idempotent" and "right-idempotent" somewhere?)

I'm pretty lost, I thought idemopotent was basically a synonym for a projection (which sounds like your #3)... do you have any links to literature using it differently?

https://en.wikipedia.org/wiki/Idempotence#Definition

That seems consistent with #3, I don't see how it's different. Operator or function, the name doesn't change anything?

Operators and functions are effectively the same thing, yeah.

In CS we normally mean #4 though ... which can technically be thought of as a variation of #3 passing/returning "the whole universe" as an argument (and including the actual arguments in the implicit lambda capture), but thinking like that only makes sense for functional programmers.

Passing the entire universe as an argument... dang... either that's deep conceptually, or I'm shallow, or both!

The wikipedia definition is directly equivalent to #1. Try rewriting it with f(a, b) = a ⋅ b.

That's not to say #3 and #1 are unrelated, though.

Where I've been lost is where the comment said "which is that there are several different (but related) things"... if they're equivalent then isn't this just making my point?

Definition 3 is the same as definition 1. Defn. 3 is idempotence (in the sense of defn. 1) of the function f under function composition. In other words, f ∘ f = f.

A valuable insight, but doesn't that come with a caveat. Def 3 is only def 1 when the 'x' in def 1 is a function or an operator or some kind. If it's "truly a value" then x is instead an identity value and not idempotent isn't it?

And for #1, what if "f" is a function that selects the first of the two arguments? Then the relation in #1 holds true for all values of 'x', but that doesn't feel like idempotency to me. And we definitely can't say that 'x' is idempotent. As 'x' defined to be "add1" wouldn't be idempotent according to the definition, but would pass the relation if "f" is fst().

I think #1 only holds under compose or 'f's that are similar to compose when 'x' is a function. And at that point you've added so many restrictions you've made definition 3. So I think I disagree with definition #1 as being a def of idempotency.

I've renamed the variables for clarity. So now your comment can be stated as:

  v = h (no longer f)
  f = ∘

But when we're trying to bring clarity to the masses, remember that most people don't think in higher-order functions, so it is certainly necessary to state them separately.

Reply on news.ycombinator.com