Re: Idempotence and "Replication Insensitivity" are equivalent ?

William Hughes wrote:
> Marshall wrote:
>
> The question posed by the title of this thread "are idempotence
> and replication insensitivity equivalent?". Since idempotence
> only applies to functions of the type A,A->A we get that
> idempotence only applies to a restricted set of functions
> on M(A). Since this restricted set does not include all
> the functions we would like to apply the term "replication
> insensitive" to, I would conclude that the terms
> "idempotent" and "replication insensitive" are not equivalent.

Well, they were never proposed to be *equivalent*, at least not by me. The two kinds of functions have different types, for one thing. They certainly look *related* though.

The proposal is that an aggregate function defined by a fold of a function f will be "duplicate insensitive" iff f is idempotent. Chris has pointed out the additional requirement that the starting value for the fold has to be an identity of f.

Has there been a counterexample? I went back over the thread and I couldn't find one; however my eyes started glazing over after rereading about 30 posts. There have been quite a few posts proposing counterexamples, but none of them have held up, again assuming I didn't miss something critical.

Anyway, do you have a counterexample? Please bear in mind that:

1. I agree that "idempotence" only applies to functions of type A, A -> A
2. I agree that an arbitrary function of type {|A|} -> B might be duplicate insensitive but not have an associated idempotent binary function. (For example, the function:

  f:{|A|} -> nat
  f(x) = 7
)

Marshall Received on Thu Sep 21 2006 - 07:11:21 CEST