3 ms·

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 t

by o11c 2y ago

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`)

dataflow 2y ago
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?
- GrantMoyer 2y ago
  https://en.wikipedia.org/wiki/Idempotence#Definition https://en.wikipedia.org/wiki/Idempotence#Definition
  - dataflow 2y ago
    That seems consistent with #3, I don't see how it's different. Operator or function, the name doesn't change anything?
    - o11c 2y ago
      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.
      - thelittleone 2y ago
        Passing the entire universe as an argument... dang... either that's deep conceptually, or I'm shallow, or both!
    - GrantMoyer 2y ago
      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.
      - dataflow 2y ago
        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?
GrantMoyer 2y ago
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.
- BoiledCabbage 2y ago
  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.
- o11c 2y ago
  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.
contravariant 2y ago
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.
- GrantMoyer 2y ago
  You don't need associativity: (x ⋅ x) ⋅ x (x) ⋅ x x ⋅ (x) x ⋅ (x ⋅ x)
  - a1369209993 2y ago
    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.
- o11c 2y ago
  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?)

by o11c 2y ago

dataflow 2y ago

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?

GrantMoyer 2y ago
https://en.wikipedia.org/wiki/Idempotence#Definition https://en.wikipedia.org/wiki/Idempotence#Definition
- dataflow 2y ago
  That seems consistent with #3, I don't see how it's different. Operator or function, the name doesn't change anything?
  - o11c 2y ago
    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.
    - thelittleone 2y ago
      Passing the entire universe as an argument... dang... either that's deep conceptually, or I'm shallow, or both!
  - GrantMoyer 2y ago
    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.
    - dataflow 2y ago
      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?

GrantMoyer 2y ago

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.

BoiledCabbage 2y ago
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.
o11c 2y ago
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.

contravariant 2y ago

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.

GrantMoyer 2y ago
You don't need associativity: (x ⋅ x) ⋅ x (x) ⋅ x x ⋅ (x) x ⋅ (x ⋅ x)
- a1369209993 2y ago
  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.
o11c 2y ago
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?)