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

[Niklas Holsti <niklas.holsti@nospam.please>]

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

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

>>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.)
> 
> 
> 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. The phrasing in the 
definition treats the Left and Right parameters (S1 and S2 in my 
message) asymmetrically. 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.

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

   type T is (W, X, Y, Z);

    function "<" (Left, Right : T) return Boolean is
    -- This function implements the ordering:
    --     W < X < Z
    --     W < Y
    -- No other pairs are comparable.
    begin
        case Left is
           when W => return Right /= W;
           when X => return Right = Z;
           when Y => return False;
           when Z => return False;
        end case;
    end "<";

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.

Now consider two Ordered_Sets, Left and Right, with Element_Type => T. 
Let the Left set be {X, Z} and the Right set be {W, Y}. Note that X is 
not "equivalent" to Z, so the Left set is "legal" with respect to 
A.18.6(5/2), and likewise for the Right set. Let's apply the RM 
definition A.18.6(22/2) to see what Equivalent_Sets (Left,Right) should 
return:

- Left and Right are not the same set object
   so we do not return True at once.

- Left and Right have the same number of elements (2)
   so we do not return False at once.

- Now we must check each element of Left and look for an
   "equivalent" element in Right:
   - X from Left is "equivalent" to Y from Right, ok.
   - Z from Left is "equivalent" to Y from Right, ok.
   Thus Equivalent_Sets (Left,Right) returns True.

However, Right contains the element W, which is not "equivalent" to any 
element in Left. That is an example of the problem I spoke of. Moreover, 
it means that Equivalent_Sets (Right,Left) will return False, showing 
that Equivalent_Sets is not always symmetric.


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

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. It seems you understand "reflexive" to mean the 
implication

    if X = Y (using the actual "=" function)
    then
    Equivalent_Elements (X, Y) is True.

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.

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

>>For example, in the case of two
>>elements E1 and E2 in an Ordered_Set it would be very natural to require
>>that if E1 "=" E2 then we cannot also have E1 "<" E2 or E2 "<" E1, in
>>other words we should have E1 "equivalent" to E2.
> 
> 
> Yes, that is indeed implied.
> 
>   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. 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, 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 "=".

[As an aside, I think there is also a small typo in A.18.9(79/2): it 
says "pair of key values" when it should say "pair of Element_Type values".]

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.

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

Agreed for the second problem ("=" on Set elements and Sets), modulo a 
wish for better explanation of "reflexive" and "irreflexive" in the RM.

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

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .