Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: Chris Smith <>
Date: Wed, 20 Sep 2006 23:03:03 -0600
Message-ID: <>

Marshall <> wrote:
> > > fold : (f: (A, B -> B), S : M(A), e : B) -> B
> > >
> > > fold f {} e = e
> > > fold f {a} e = f(a, e)
> > > fold f {a union P(A)} e = f(a, fold2(f, P(A), e))

> I meant "fold." The "2" was left over from an earlier edit, in
> which I was differentiating between two different ways to
> do the folds. Which I mention now, why not?
> The version of fold that requires an e element is not the
> entire story, although it mostly is. There are cases where
> we do not have an identity nor a starting point, and so
> we'd be in trouble if we required one.
> 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. In PostgreSQL, for example, that distinguished value is NULL. Anticipating the howls of agony that this will trigger, you could augment B with an infinity (positive for min, or negative for max), as I said in an earlier response in this thread.

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.

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

Chris Smith
Received on Thu Sep 21 2006 - 07:03:03 CEST

Original text of this message