# Re: Idempotence and "Replication Insensitivity" are equivalent ?

Date: 20 Sep 2006 22:44:01 -0700

Message-ID: <1158817441.291755.283950_at_i42g2000cwa.googlegroups.com>

Chris Smith wrote:

> Marshall <marshall.spight_at_gmail.com> wrote:

*> >
**> > Consider min(). Min over unsigned 32 bit ints has an
**> > identity: 2^32. However, min over arbirtrary precision
**> > ints does not have an identity. Oops!
**>
**> I don't believe that's ever a real problem. You can simply add a
**> distinguished value to B, and define the function f so that it does the
**> right thing when it is passed that distinguished value.
*

Bleah. I don't like that idea, for the same reason that I also don't like either of these types for div:

/: int, int where != 0 -> int

/: int, int -> (int | undefined)

I like my div to be int, int -> int. If I pass in a zero for the divisor, go ahead and dump core, throw an exception, release the hounds, whatever. The program's clearly broken anyway.

> In PostgreSQL,

*> for example, that distinguished value is NULL.
*

Argghhh! Oooooh, the agony!

> Anticipating the howls

*> of agony that this will trigger,
*

I see you have anticipated me.

> you could augment B with an infinity

*> (positive for min, or negative for max), as I said in an earlier
**> response in this thread.
*

No, I don't like that atoll, not won bit. Don't like NaN, neither, no how.

> If you're trying to fit as many relations as possible into the category

*> of f: A^2 -> A, then I suppose it makes sense to offer the latter
**> definition, but I don't find that a very convincing reason to provide
**> two definitions. In any case, you could accomplish the same thing by
**> just allowing the infinity in your input.
*

I am convinced that would cause more problems than it would solve.

> > > Right. Given that f is associative and commutative, you are guaranteed

*> > > that fold(f,...) is well-defined. (Proof is fairly simple by
**> > > induction.) Also, in order for fold(f,...) to be well-defined, it is
**> > > necessary that *either* f must be associative and commutative, *or* e
**> > > cannot be an identity of f. (Proof: Let e be an identity of f. First
**> > > consider possible evaluations of fold(f,{a,b},e). They must be equal to
**> > > each other, so f must be commutative in order for fold(f,...) to be
**> > > well-defined. Now consider fold(f,{a,b,c}). Using the commutative
**> > > property as established above, f(f(a,b),c) must be equal to f(a,f(b,c)),
**> > > so f is associative as well.) That is still not a sufficient condition
**> > > for well-definedness in the case where e is not an identity, but I don't
**> > > see an easy sufficient condition.
**> >
**> > I'm not really following this. Your either/or above is supposed to
**> > be an exclusive or?
**>
**> No, an inclusive or. Specifically, it was meant to be: IF (f is not
**> commutative OR f is not associative) THEN e is not an identity of f.
**> There was also a typo, which I fixed above... should be f(a,f(b,c))
**> where I earlier wrote f(a,f(b,b)).
*

Ohhh. Okay. Hmmm.

Marshall Received on Thu Sep 21 2006 - 07:44:01 CEST