Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: Marshall <>
Date: 20 Sep 2006 22:44:01 -0700
Message-ID: <>

Chris Smith wrote:
> Marshall <> 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.

Well, earlier I said that either f must be associative and commutative, or else the fold has to be over an ordered collection. Does that suffice?

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

Original text of this message