From mboxrd@z Thu Jan 1 00:00:00 1970 Path: eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: "Randy Brukardt" Newsgroups: comp.lang.ada Subject: Re: Map iteration and modification Date: Sat, 30 Dec 2023 01:21:22 -0600 Organization: A noiseless patient Spider Message-ID: References: Injection-Date: Sat, 30 Dec 2023 07:20:38 -0000 (UTC) Injection-Info: dont-email.me; posting-host="2d85733152c498363b0c58151a247659"; logging-data="1281387"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19NChOAyppx6WwFBS20fBTN3Y7kKNQNtYY=" Cancel-Lock: sha1://AITMHGILA8z6BkpxGHg55RDtQ= X-Newsreader: Microsoft Outlook Express 6.00.2900.5931 X-Priority: 3 X-RFC2646: Format=Flowed; Response X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.7246 X-MSMail-Priority: Normal Xref: news.eternal-september.org comp.lang.ada:65946 List-Id: "Dmitry A. Kazakov" wrote in message news:umm4r5$ppag$1@dont-email.me... > On 2023-12-29 04:20, Randy Brukardt wrote: >> "Dmitry A. Kazakov" wrote in message >> news:umk6ds$e9hc$1@dont-email.me... >> ... >>> Provided a sane implementation of map. >>> >>> 1. It is safe to loop over the map items in the *reverse* order of, >>> deleting whatever items. >> >> A sane implementation of a map does not have/require an ordering of keys. > > Yes, but iterating a map requires ordering regardless properties of the > keys. Only as far as there is an order implied by the order that things are returned. That order doesn't have any meaning, and certainly there isn't any such thing as "forward" or "reverse" to it. (Which was the original claim, after all.) There is no "natural" order to the key/element pairs; they are effectively unordered. ... >> So >> the idea of "reverse" or "forward" does not make sense for a general map. >> (There are, of course, special cases where the keys have an order that >> matters to the map; the standard ordered map is like that.) Assuming an >> ordering is exposing the implementation unnecessarily. > > It always does sense *IF* enumeration (needed for iteration) is provided. > Enumeration of pairs (, ) is not same as ordering values by > the keys. True, but it doesn't imply any particular ordering. Certainly, no concept of "forward" or "reverse" applies to such an ordering (nor any stability requirement). Practically, you'll get the same order each time if the container isn't modified, but if it is, all bets are off. (If the container is changed by element addition or deletion, the index may get rebuilt [hash table reconstructed if too full, tree-index rebalanced, etc.] and that can change the iteration order dramatically.) ... > No. First, it is two different interfaces. A view of a map as: > > 1. An ordered set of pairs (, ) This is not a map (in general). There is an *unordered* set of pairs. You can retrieve them all, but the order that is done is meaningless and is an artifact of the implementation. There's a reason that maps don't have reverse iterators. > 2. A mapping -> > > Second, the point is that both are array interfaces. The first has > position as the index, the second has the key as the index. "Position" is not a property of an (abstract) map. That's my complaint about looking at everything as an array -- one starts thinking in terms of properties that things don't have (or need). > Both are invariant to removal a pair and any *sane* implementation must be > OK with that. The only sort of position that you could possibility talk about for a map is the ordinal order that an iterator returns key/element pairs. But that necessarily changes when you insert/delete a pair, as that pair will occur at some (unspecified) point in the ordinal order. Otherwise, you won't have the performance expected for key lookup in a map. > The problem is not whether you allocate pairs individually or not. The > insanity begins with things unrelated to the map: > > 1. OOP iterator object. > > 2. FP iteration function. > > Both are bad ideas imposed by poor programming paradigms on implementation > of a clear mathematical concept. That comes with constraints, assumptions > and limitation array interface do not have. ??? Abstractions are "poor ideas"? You have some problem with an iterator interface as opposed to an array interface?? That make no sense at all given your other positions. > for Index in reverse Map'Range loop > Map.Delete (Index); > end loop; > > would always work. It only works if you think of Map'Range as an iterator object. Otherwise, you would have to impose an extra "position" interface on the map (or other container), and at a substantial additional cost in time/space. Containers in general don't have "positions", elements are unordered unless the container imposes one. ... > Arrays have interface and implementation. The array interface is a mapping > key -> value, the most fundamental thing in programming. That's only part of it. It also includes the idea of "position", including calculated positions, the operations of concatenation and slicing, and (for Ada at least) ordering operations. If the array interface was *only* a mapping I would not object to it. Maps do not have a natural order, and nothing should be depending on such order. There is no meaning to the third pair in a map. > An array implementation as a contiguous block of values indexed by a > linear function is a basic data structure that supports the interface. Right: the much more complex interface I note above. And that's the problem. You don't even seem to realize all of the unnecessary baggage that arrays carry with them. ... > Sure. The problem with Ada is that it does not separate array interface > from its built-in array implementation and does not separate record > interface and implementation either. Not arguing this. (Other than this is way down the list of problems with Ada, there are many that are worse.) ... > Now, tell me that you have a longstanding objection to the entire concept > of records... (:-)) Nope. There has to be a hetrogenous grouping of values, and records do it as well as anything else. I do agree that more abstraction would be nice. The problem with arrays is that the mapping part is tied to many other supposedly fundamental capabilities that aren't fundamental at all. Even intellegent people such as yourself have been using arrays so long and so primitively that you've gotten blinded to the fact that basic data structures really have only a handful of operations, and the majority of the "fundamental" capabilities aren't needed much of the time and certainly should only be provided when needed. Randy.