Re: GCC 4.0 Ada.Containers Cursor danger.

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

On Fri, 15 Jul 2005 01:03:34 +0200, Georg Bauhaus wrote:

> Mikhail Terekhov wrote:
> 
>>     - First is that all containers have an order.
>>       Again, sets and hashes in general are *not ordered*.
>>       To impose an order on them standard needs to put a
>>       restriction on implementarion algorithms.
> 
> Ada.Containers require that the elements of a set say can be
> had one after the other through iteration using cursors.
> I can hardly think of this as a restriction in practice.
> On the contrary, why should I be satisfied with just membership
> test? Or with a fixed set of operations on sets? Or why should I
> abandon sets in favor of some other containers, because they
> fit better with someone's ideas of how a mathematical structure
> is sometimes defined? ;-)
> 
> Say I want a subset B of A,
>
>   B := {x: x in A | x >= 0};
> 
> This could be done using a generic algorithm which is similar
> to the Generic_Find algorithm that Matt has presented in that
> there will be a generic formal procedure that acts
> as the predicate ">= 0?".

See the well-ordering theorem and then the axiom of choice. (:-))

Think about differences between:

- An unordered set of unordered elements
- An unordered set of ordered elements
- An ordered set of unordered elements
- An ordered set of ordered elements (and these orders are different)

>> You example
>>       is completely legal generic function in the current
>>       Ada.Containers framework. But if you decide at some
>>       point to add unordered containers, then you generic
>>       function became invalid because for unordered containers
>>       "first" and "last" have no sence at all.
> 
> For me, First and Last (or whatever you call them) *do* make sense
> for any reasonable notion of a set in programming, sorted or not,
> even when used in computer science.

Hmm, what about ring buffers?

> Their purpose then is to start and end the enumeration of the elements
> in the set. You can think of cursors as elements of a mathematical
> index set (yes!) that is associated with the elements in some set.
> Such as is used for example in proofs by induction, or when you want
> to transform a set into a sorted set, etc.

And for proofs it is essential that the premises were correct. Programming
is not much different...

> I find Cursors useful when I want to put an index set into operations
> inside a computer. When I'm can use any container,
> how could I implement index sets without Cursors?

You are mixing implementation and interface.

>>     - Second is that find/search operation makes sence only
>>       for a mapping container i.e. vector or hash;
> 
> Find is a membership test, how could it not make sense for
> a set?

No. Find is more general. It searches for an element E in S having a
certain property f(E). Find is a membership test for X only when f(E) is
E=X.

[and again, sets could be searchable and not]

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