From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,f5142427a147e149 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news3.google.com!news.glorb.com!news.tele.dk!feed118.news.tele.dk!news.tele.dk!small.news.tele.dk!tiscali!newsfeed1.ip.tiscali.net!fi.sn.net!newsfeed2.fi.sn.net!news.song.fi!not-for-mail Date: Wed, 24 Jan 2007 01:04:38 +0200 From: Niklas Holsti User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.8) Gecko/20060628 Debian/1.7.8-1sarge7.1 X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Equivalent keys/elements in Ada.Containers Maps and Sets References: <45b60602$0$24602$39db0f71@news.song.fi> <1169567122.501077.189450@s48g2000cws.googlegroups.com> In-Reply-To: <1169567122.501077.189450@s48g2000cws.googlegroups.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Message-ID: <45b69499$0$31527$39db0f71@news.song.fi> Organization: TDC Song Internet Services NNTP-Posting-Host: laku61.adsl.netsonic.fi X-Trace: 1169593497 news.song.fi 31527 81.17.205.61:32975 X-Complaints-To: abuse@song.fi Xref: g2news2.google.com comp.lang.ada:8451 Date: 2007-01-24T01:04:38+02:00 List-Id: 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 . @ .