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

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

Matthew Heaney wrote:
> 
> 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>

I don't find the word "weak" in the RM paragraphs that define the 
expected properties of "<", in A.18.6(56/2) for Ordered_Maps and 
A.18.9(79/2) for Ordered_Sets. Both paragraphs just say "strict ordering".

Moreover, these paragraphs then expand "strict ordering" into 
irreflexive, transitive and "asymmetric", not "antisymmetric", and they 
say nothing of equivalence (really "incomparability") being transitive. 
So your "exact requirement" does not match the RM wording. I think the 
RM wording should be changed to make them match.

I did not know that the term "weak" is used for this kind of ordering. 
Had I known that, perhaps I could have described my points better.

The definitions of these mathematical terms on Wikipedia don't seem 
universal because Wikipedia refers to "some contexts" and "other 
contexts" in which the terms are used differently, and Wikipedia is 
anyway not a good authority for the Ada RM. Moreover, mathematical terms 
like "reflexivity" can be tricky to use in a situation where X = Y does 
not mean X that can be substituted for Y in any expression E(Y), as it 
cannot for Ada expressions. I should prefer the RM to speak more 
concretely of logical connections between Ada expressions, with less use 
of mathematical terms like "reflexive relation".

You and I agree completely that the "<" function for the Ordered 
containers *should* be such that the "equivalence" (incomparability) 
relation is transitive, so we don't have to argue about that. The only 
open question is if and how the RM currently expresses this requirement, 
or this expected behaviour of the "<" function.

My examples of other kinds of "<" functions were only meant to test the 
RM wordings. I did not and still don't see where the RM explicitly 
requires the "incomparability" relation to be transitive.

I have sent a message on this issue to ada-comment@ada-auth.org and I 
suggest that the discussion should be continued there.


>>>>-- Second problem: "=" for Element_Type in Sets

I will send a message on this issue to ada-comment@ada-auth.org and I 
suggest that this discussion, too, should be continued there.

I'll only say here that I did not intend to offend you by "imputing" any 
"beliefs" to you; I was only explaining where I thought we might be 
understanding the RM differently, based on our discussion. I'm sorry if 
  I offended.

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