Re: Map iteration and modification

["Randy Brukardt" <randy@rrsoftware.com>]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:umm4r5$ppag$1@dont-email.me...
> On 2023-12-29 04:20, Randy Brukardt wrote:
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> 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 (<key>, <value>) 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 (<key>, <value>)

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 <key> -> <value>
>
> 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.