Re: Map iteration and modification

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On 2023-12-30 08:21, Randy Brukardt wrote:
> "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.

Iteration = order. It is the same thing. If you provide iteration of 
pairs in the mapping by doing so you provide an order of.

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

It does. You have a strict total order of pairs which guarantees 
existence of previous and next pairs according to.

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

True, an operation may invalidate whatever invariants. It applies 
equally to any orders, any cursors and pointers, any hidden states of 
pending foreach operations. Sanity means which invariants the 
implementation keeps.

I would argue that for general-case containers keeping 
iterators/pointers and hidden states would be far more difficult than 
keeping an order.

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

Unless you provide iteration of the map. Most applications want 
iteratable maps. Then a finite maps is still iteratable regardless best 
efforts, though by crude means. E.g. once have an array (ordered set) of 
keys, you are done.

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

Yes position is a property of enumeration.

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

It is the reverse. Iterators is secondary to the order. Iterator walks 
pairs in the order of pairs = in the order their positions.

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

If you provide a random order, then yes. This is what an "insane" 
implementation would do. A "sane" implementation would deploy orders 
with reasonable properties. E.g. an obvious: k1/=k2/=k3 then (k1,v1) < 
(k2,v2) is preserved when (k3,v3) is added or removed.

>> 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"?

Neither is an abstraction [as they are not entities of the problem 
space, but programming techniques artifacts, [anti-]patterns]. Iterator 
is an object of an unrelated type. Foreach is a stateful operation 
unrelated to the pure map interface.

> You have some problem with an iterator
> interface as opposed to an array interface??

Yes, I am against pointers (referential semantics) in general. BTW, Ada 
should have abstract pointer interface allowing the programmer to 
implement iterators = fat pointers.

[ It would be fun with the pure unordered maps you suggested, the 
implementation of the pointer (iterator) would keep an array or an 
ordered set of keys... (:-)) ]

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

Yes, I would impose positions in all general case containers.

Specialized very large containers where an implementation without 
cashing would become O(log n) rather than O(1) deploy other means of 
traversal anyway.

>> 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",

Yes. Position in array is a mapping key/index <-> Natural.

> including calculated positions,

Yes. Natural numbers have numeric operations.

> the operations of concatenation and slicing,

That depends, but like with maps, it is expected. Maps as containers are 
expected to provide "concatenations" of pairs (set-theoretic union) and 
slicing (submaps). Because mathematically maps are sets of pairs and 
sets can be manipulated in many ways. Ordering does not add much to the 
interface.

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

Yes, but those are not iteratable. We are talking about maps one can 
iterate. That requires an order. The question is only about the forms of 
exposure of that order in the interface. My objection is that iterators 
and foreach are poor forms.

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

I don't see anything that is not already there. What are reasons for not 
providing:

    M (n)       [ e.g. M (n).Key, M (n).Value ]
    M (n1..n2)  [ in mutable contexts too ]
    M'First
    M'Last
    M1 & M2     [ M1 or M2 ]

They are all well-defined and useful operations.

> The problem with arrays is that the mapping part is tied to many other
> supposedly fundamental capabilities that aren't fundamental at all.

I disagree in the case of 1D arrays. There is of course interesting 
issues with nD arrays but that is where multiple inheritance kicks in, 
because in mathematics you can have "continuations" of concepts in more 
than one direction. So 1D array might be both an nD array and something 
else too.

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

That is true. But again, it is solved by inheritance already. You can 
have an unordered map interface separately inherited by a general-case 
map. You can split interfaces to refine what operations they include 
from the implementation constraints point of view. So you can have a 
very flexible mesh of implementations sharing some interfaces, but not 
others. The best example is, of course, various types strings.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de