Re: Equivalent keys/elements in Ada.Containers Maps and Sets

["Randy Brukardt" <randy@rrsoftware.com>]

"Niklas Holsti" <niklas.holsti@nospam.please> wrote in message
news:45b69499$0$31527$39db0f71@news.song.fi...
> Matthew Heaney wrote:
> > Niklas Holsti wrote:
> >
> >>-- First problem: "equivalence" in Ordered Maps and Sets
> >>
> >>However, one can easily make
> >>an example of a strict ordering "<" in which the "incomparable" relation
> >>is not transitive; say we have three values X, Y, Z where the only
> >>relation is X < Z; thus X and Y are incomparable and Y and Z are
> >>incomparable, but X and Z are not incomparable.
> >
> >
> > I don't see this.  Please provide an example.
>
> Those X, Y, Z *were* the example, but let's make it clearer:
>
>     type T is (X, Y, Z);
>
>     function "<" (Left, Right : T) return Boolean is
>     begin
>        return Left = X and Right = Z;
>     end "<";
>
> This function "<" is a strict ordering relation for T, as required for
> Ada.Containers.Ordered_Maps/Sets. But the "equivalence" relation induced
> by this "<" is not transitive: X and Y are "equivalent" (both X < Y and
> Y < X are False) and Y and Z are "equivalent" (both Y < Z and Z < Y are
> False) but X and Z are not "equivalent" (because X < Z is True).

I don't believe this function meets the requirements. It has to be the case
that the function is reversible (we can't know the order of the operands)
and it can't be the case that
   neither (X < Z) nor (Z < X) nor (X = Z) (where "=" means equivalent).

One of these three things has to hold, or the function is not acceptable.

> Of course this "<" is not a complete ordering, but that is not required
> in the RM and I'm sure it was not the intention to require it (because
> then "equivalence" would reduce to "identity").

The basic idea of equivalence is to allow case-insensitive keys. Of course,
it doesn't make sense to just support case-insensitive keys.

But I do think you need a complete ordering, in the sense that things that
are not equivalent have to have one of X < Y or Y < X be true.

I haven't a clue as to what wording is missing. The original wording that
Matt and I had proposed simply gave a bunch of relationships that had to be
true. Then the mathemations got at it and rephrased it into mathematical
terms that make it hard to tell if it is actually right. (I can never
remember which is which of reflective, transitive, and symmetric). I simply
gave up at that point and trusted them...

...
> The "equivalence" relation derived from this "<" relation makes
>
>     X "equivalent" to itself and Y
>     Y "equivalent" to itself and X and Z
>     Z "equivalent" to itself and Y
>     W "equivalent" to itself only.

That cannot be an acceptable equivalence relationship. There are disjoint
sets of equivalent elements, and every element belongs to exactly one set.
For ordered cases, there is a complete ordering between the sets. For hashed
cases, each set has its own hash value. If the RM language doesn't imply
those things, it is wrong.

But if you think the RM language is wrong, please also tell us how to fix
it. Just saying it is wrong is no help whatsoever. (Well, at least not for
me.)

...
> >>-- Second problem: "=" for Element_Type in Sets
> >>
> >>For Sets, however, I find it puzzling that no relationship is required
> >>or expected between this "=" and the other formal functions
> >>Equivalent_Elements, Hash and "<".
> >
> >
> > Equality implies equivalence, so there is no puzzle.  (But note that
> > equivalence does not imply equality -- hence two separate generic
> > formal functions.)

Well, equality *ought to* imply equivalence. But Matt, you can't reason from
what was intended, but rather what the RM words require.

> Aha - I think I see where this arises for Hashed_Sets. The RM in
> A.18.8(66/2) requires the actual for Equivalent_Elements to be
> "reflexive". I understood this to mean that Equivalent_Elements (X, X)
> should always be True.

No, Matt is just reasoning from what he'd like to be true, not what the RM
implies. You'll note he didn't give any RM paragraph references.

...
> Thanks for your answer, which clears up my "second problem". I
> misunderstood the meaning of "reflexive" and "irreflexive" because the
> RM paragraphs did not explain how these terms related to the actual "="
> function. I'm now also satisfied with the definition of "=" on Sets.

Well, I'm not. I don't believe Matt was referring in any way to the actual
wording of the RM. I don't see any wording that would require any
relationship between "=" and Equivalent_Elements, and this is needed.

> > Yes, they were indeed considered, and are already implied by the RM.

Nothing is "implied" by the RM. Please explain how you think that these
issues are covered by the RM wording, as opposed to what we intended the RM
to say.

> Should I submit these comments to ada-comment@ada-auth.org?

Yes, because the people who could give you a better mathematical example
than Matt or I can don't come here. And the discussion of the problem should
be on the record, not hidden here where it will never be seen again.

                                 Randy Brukardt, ARG Editor