Re: Map iteration and modification

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

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:umotm2$18lqm$1@dont-email.me...
...
>> 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.

Certainly not. An iteration presents all of the elements in a container, but 
there is no requirement that there is an order. Indeed, logically, all of 
the elements are presented at the same time (and parallel iteration provides 
an approximation of that).

If you try to enforce an order on things that don't require it, you end up 
preventing useful parallelism (practically, at least, no one has succeeded 
at providing useful parallelism to sequential code and people have been 
trying for about 50 years -- they were trying when I was a university 
student in the late 1970s).

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

Again, this is unrelated. Iteration can usefully occur in unordered 
containers (that is, "foreach"). Ordering is a separate concept, not always 
needed (certainly not in basic structures like maps, sets, and bags).

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

Ada requires that cursors continue to designate the same element through all 
operations other than deletion of the element or movement to a different 
container. Specific containers have additional invariants, but this is the 
most general one. No other requirement is needed in many cases.

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

Surely not. This is a basis for my disagrement with you here. The only 
requirement for enumeration is that all elements are produced. The order is 
an artifact of doing it an inherently parallel operation sequentally. We 
don't care about or depend on artifacts.

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

Nope, this is completely wrong. Once you start with a bogus premise, of 
course you will get all kinds of bogus conclusions!!

...
>> You have some problem with an iterator
>> interface as opposed to an array interface??
>
> Yes, I am against pointers (referential semantics) in general.

This is nonsense - virtually everything is referential semantics (other than 
components). Array indexes are just a poor mans pointer (indeed, I learned 
how to program in Fortran 66 initially, and way one built useful data 
structures was to use array indexes as stand-ins for pointers). In A(1), 1 
is a reference to the first component of A.

So long as you are using arrays, you are using referential semantics. The 
only way to avoid it is to directly embed an object directly in an enclosing 
object (as in a record), and that doesn't work for many problems.

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

Performance. If all of these things are user-definable, then one has to use 
subprogram calls to implement all of them. That can be very expensive, 
particularly in the case of mutable operations (and mutable slices are the 
worst of all). Moreover, since one would want the ability to have generic 
and runtime parameters that only meet this interface (and the ability to 
pass slices to subprograms that take unconstrained array parameters), you 
would have to be able to pass all of these subprograms along with 
parameters, even when you don't need them. That would make array operations 
far more expensive than they are today.

I think it is much better to get rid of most of these operations as built-in 
things and just let the programmer build their own operations as needed. 
That keeps the cost confined to those who use them. Distributed overhead is 
the worst kind, and slices in particular have a boatload of that overhead.

                Randy.