Re: Generic Package

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

"Markus E Leypold"
<development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> wrote in
message news:40irbbzm2t.fsf@hod.lan.m-e-leypold.de...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
>
> > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
> > news:1ozvzzh59ebq8$.yeh9do8s3hig$.dlg@40tude.net...
> >> On Tue, 01 May 2007 15:42:21 +0200, Georg Bauhaus wrote:
> > ...
> >> > Yes, in the sense that the specifics of memory layout and such are
> >> > unknown and irrelevant to the client; in particular, no order needs
> >> > to be specified.
> >>
> >> Apart from obvious uselessness of contracts referencing to the memory
> >> layout, the above is self-contradictory. Memory layout defines an
order.
> > It
> >> also is a part of the contract. Hence the interface is ordered.
> >
> > And now all is clear.
>
> No. The only thing that is clear to me, is, that DK is splitting hairs
> again, just to win the argument.

Maybe, but that's just name calling and is never an appropriate way to
conduct an argument. Besides, you're going to claim the same about me in
your reply to this message... ;-)

> > It is impossible to implement a set with having some form of order. So,
for
>                       ^^^^^^^^^
>
> Implement, yes. But it is possible to implement a set interface
> without forcing the user to provide an order function to instantiate
> the set. It is also possible to provide a mechanism for such an
> implementation that gives you all the elements in this set in some
> arbitary order/sequence which might change with every invocation. This
> is called iteration.

You're repeating the obvious. But a set where you don't specify the order is
still an ordered set: there exists an order between the elements, even if
you don't know what it is and don't have to describe it.

> DK originally stated, it is not possible to iterate over an unordered
> set: It is.

I actually agree with DK, using his definitions. The problem is that no such
set could ever be constructed (even on a piece of paper, the elements have
an order). So the fact is completely irrelevant: there is no such thing as
an unordered set.

> It is possible to specify the contract for this iteration without
> referring to an order (I did it in one of my recent post). DK denied
> this. He is wrong.

Of course you can if you assume primitives that effectively give you an
order. It's like specifying a contract for set inclusion: you certainly can
do so, but it is unlikely to say anything interesting: it's mostly likely
going to be a tautology.

> Implementing a set as a linked list might not be efficient enough for
> a large number of items -- still: It is a set in any sane sense and
> one can provide an interface to iterate over the items. And it has
> even been implemented without using an order defined on the elements
> of the set.

Yes, and so what? It still has an order between elements. That order doesn't
have to be determined by the values of the elements, as you seem to be
assuming. It could be determined by the address of the memory used or the
ordering of some handle type, or by phase of the moon. But it isn't possible
to have a set of elements without some order (at least on the sorts of
machines that Ada was intended to program).

> So the even the statement "one cannot implement a set (with or without
> iteration) without providing an order over the elements" is plainly
> wrong.

A linked list sure;y provides an order for the elements. Why you insist on
that order coming from the outside is beyond me. Even as hashed set doesn't
meet your requirements for "order", which is completely ridiculous.

> (And no: The linked list doesn't define an order on all possible
> elements of the set.)

An who cares about that? Any particular set of elements has an order. I
don't much care if a different set object has a different order on the same
elements. It's irrelevant. "An order" is not the same as "a defined order"
or "the same order for any pair of elements with the same value".

Indeed, any ordering between the values of the elements is completely
unrelated to the abstract set properties. Any operations that depend on such
an order are not set operations at all.

In any case, this is an Ada forum, and abstractions that you cannot describe
in Ada are simply not relevant (certainly not as the basis of containers).
Any Ada implementation will have some implied ordering between the elements
in the set.

My contention always has been that "sets" are an irrelevant abstraction from
a programming perspective. They're too inefficient to use for any purpose.
What Ada.Containers calls a set is really a map where the keys are included
as part of the elements. Yes, they have some set operations because some
people thought if they were called sets they should have those operations. I
would have preferred choosing a more sane name, but whatever.

And I would hope that I was done reading this bulls***, but I'm sure I'm
not...

                           Randy.