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

["Matthew Heaney" <mheaney@on2.com>]

On Jan 23, 6:04 pm, Niklas Holsti <niklas.hol...@nospam.please> wrote:
> Matthew Heaney wrote:
> > Niklas Holsti wrote:
>
> 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.

The exact requirement is for a "strict weak ordering"; that is,
irreflexive, antisymmetric, transitive, and equivalence is transitive
(where equivalence is defined as x < y and y < x are both false).

<http://www.sgi.com/tech/stl/StrictWeakOrdering.html>
<http://en.wikipedia.org/wiki/Strict_weak_ordering>


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

Right, which is why your less-than operator doesn't specify a strict
weak ordering.  Hence it is not an acceptable as a generic actual for
ordered associative containers.


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

Yes, for a total ordering, equivalence is the same as equality, and no,
that's not required by the RM (which is why there are two generic
formal operators, and why ordered sets have both an equality operator
and an Equivalent_Sets operation).


> >>For example, by A.18.7(22/2) the function Equivalent_Sets reports two
> >>sets S1 and S2 as equivalent if they have the same number of elements
> >>and if for every element E1 of S1 there is an element E2 of S2 such that
> >>E1 and E2 are "equivalent". (Note the asymmetry of this definition: it
> >>"traverses" S1 and "searches" for equivalent elements in S2.)

I don't know why you think the "asymmetry of the definition" is
significant.  The Equivalent_Sets operation is of course symmetric.


> > The search only applies to the hashed set.  (A search is necessary
> > because hashed containers can have different capacities.)  For the
> > ordered set, you only need to traverse both sets simultaneously; there
> > is no search.
>
> I'm speaking of the way the Equivalent_Sets function is *defined* in the
> RM, not about how it might be implemented.

It works out to be the same.  The RM is technically correct here.  An
implementation of Equivalent_Sets could certainly search the right-hand
set for the current element of the left-hand set, but in practice no
implementation would ever do it that way.


> The phrasing in the
> definition treats the Left and Right parameters (S1 and S2 in my
> message) asymmetrically.

So what?  Equivalent_Sets is symmetric.


> A symmetric phrasing would be something like:
> the elements in the Left and Right sets can be paired one-to-one such
> that the two components in each pair are "equivalent". But this is not
> the way the RM is written.

Yes, and Pepsi tastes different from Coke!  Again, so what?


> >>Now, if "equivalence" of elements is not transitive, we can have two
> >>sets S1 and S2 such that Equivalent_Sets (S1, S2) is True even if S2
> >>contains an element that is not "equivalent" to any element in S1.

Equivalence must be transitive, otherwise this would not be a strict
weak ordering.


> > I still don't know what you mean by equivalence not being transitive.
> > Please provide an example.

> See above, the "<" for type T, but now I'll expand it a bit to show the
> consequence for Equivalent_Sets, for which I need four values of the
> Element_Type T:

Your definition is not a strict weak ordering.


> >>-- Second problem: "=" for Element_Type in Sets
>
> 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.

Yes, of course Equivalent_Elements is reflexive.


> It seems you understand "reflexive" to mean the
> implication
>
>     if X = Y (using the actual "=" function)
>     then
>     Equivalent_Elements (X, Y) is True.

I don't know why you'd think this has anything to do with what "I
understand reflexive to mean".  Equivalence is reflexive, and equality
is reflexive, but that has nothing to do with the separate requirement
that equality implies equivalence.


> This is, of course, a much stronger requirement, and inded it relates
> the actual functions for "=" and for Equivalent_Elements in exactly the
> way that I wanted.

It has nothing to do with what anyone wants.  It simply wouldn't work
otherwise!


> So here I would just like the RM to explain more clearly what it means
> by "reflexive", with reference to the actual "=" function.

That "=" is reflexive is implied by the meaning of equality!  You're
not free to define "=" willy-nilly.


> >   E1 = E2 => Is_Equivalent (E1, E2)

> Aha - again. The RM in A.18.9(79/2) requires the actual for "<" to be
> "irreflexive". I understood this to mean that X < X is always False.

Um, yeah.


> It seems that you understand "irreflexive" to mean the implication
>
>     if X < Y (using the actual "<" function)
>     then
>     X /= Y (using the actual "=" function).

Again, you are imputing beliefs to me that have nothing to do with what
I think nor what is implied by the RM.

Your implication is also backwards.  It should be:

  "=" (X, Y) => not "<" (X, Y) and not "<" (Y, X)

That is, equality implies equivalence.


> Again, this is a stronger requirement and what I was hoping for, so
> again I would only wish that this RM paragraph would explain
> "irreflexive" more clearly, with reference to the actual for "=".

No.  You're confusing reflexivity of equality and reflexivity of
equivalence with a distinct implication, that equality implies
equivalence.


> I still have the first problem (possible non-transitivity of the
> "equivalence" relation defined by "<") and its effect on Equivalent_Sets
> for Ordered_Sets.

There is no problem.  Equivalence must be transitive, since that is
what "strict weak ordering" means.  (Without transivity of equivalence,
then this would be a mere partial ordering, not a strict weak
ordering.)

Regards,
Matt