From: "Alexy V Khrabrov" <khrabrov.a@worldnet.att.net>
Subject: Re: Wanted: Ada STL. Reward: Ada's Future
Date: 1999/02/01
Date: 1999-02-01T00:00:00+00:00 [thread overview]
Message-ID: <7931ej$qqf@bgtnsc02.worldnet.att.net> (raw)
In-Reply-To: m3n22z6ifj.fsf@mheaney.ni.net
Matthew Heaney wrote in message ...
>On the contrary, a set is next-to-useless as a collection abstraction in
>any real program.
On the contrary, set is a useful abstraction. In fact, it's the first
abstaction in mathematics, used by Euclid to prove that the SET of primes is
infinite. Set was used by Euler, Bernoulli, Gauss, Turing, and others,
before you or I were born, Matthew, and will be used after us, Ada, C++, or
computers in general, for that matter.
Set is a part of C++ STL which is used all the time, and emphasized in all
STL books.
I've seen a gazillion programs using lists for mimicing set behavior, and
will see a bazillion more.
>A set is an unordered collection without duplicates.
Not necessarily unordered. A very useful extension of math set is a set of
ordered items, for which a generic taking an "<" parameter along with the
Element type and "=" is most suitable form in Ada.
That's how in fact the best Ada ADTs I've seen so far, LGL components, were
written:
http://lglwww.epfl.ch/Components
>The problem with a
>set is that when you add an item to the set, you have to check the
>entire set to make sure that the item isn't already in the set.
If it's ordered as above, the search is as efficient as an AVL tree search
[read -- any] can be.
>That's fine if that's the behavior you want. However, it has been my
>personal experience that this is not the abstraction you require.
And I do require sets, as many other people do, too. Real world contains
sets, and any faithful OOP will need them.
>Typically, all you need is an abstraction for an unordered collection.
>When you add an item to the collection, it puts (a copy of) the item in
>the collection, without any checks.
I prefer ordered sets whenever I can supply the "<" -- and I almost always
can. Give me one example where you can't. I can even sort files on their
last access time, can't I? Tasks on their name, etc. -- even limited
private types, that is.
>The problem with many data structure texts is that they omit any
>discussion of this important abstraction. And so everyone goes through
>life thinking that a set (or multiset) is the only kind of unordered
>collection that exists.
And they also omit ordered sets.
>In my work on the ACL (which I suspended until gnat 3.11p came out: it
>wouldn't compile otherwise), I call this kind of abstraction a
>"container." There is only a minimal set of operations on a Container
>type:
>
>o add an item to the container
>
>o iterate over items in the container
>
>o remove the item currently designated by an (active) iterator
Where is your ACL? Is it public?
>The first thing in the morning you need a Container, not a Set.
Well, and I need sets, buddy!
Cheers,
Alexy V. Khrabrov
UPenn CIS/NEC Research Institute/Princeton/CMSC
next prev parent reply other threads:[~1999-02-01 0:00 UTC|newest]
Thread overview: 102+ messages / expand[flat|nested] mbox.gz Atom feed top
1999-01-31 0:00 Wanted: Ada STL. Reward: Ada's Future Alexy V Khrabrov
1999-01-31 0:00 ` Simon Wright
1999-02-01 0:00 ` Jeff Carter
1999-02-08 0:00 ` Michael F Brenner
1999-02-01 0:00 ` Stanley R. Allen
1999-02-01 0:00 ` dennison
1999-02-01 0:00 ` Jerry van Dijk
1999-02-01 0:00 ` Marin David Condic
1999-02-01 0:00 ` Matthew Heaney
1999-02-01 0:00 ` Alexy V Khrabrov [this message]
1999-02-01 0:00 ` Matthew Heaney
1999-02-01 0:00 ` Jeff Carter
1999-02-01 0:00 ` Brian Rogoff
1999-02-01 0:00 ` Ehud Lamm
1999-02-02 0:00 ` Pointer Arithmetic (was: Wanted: Ada STL....) adam
1999-02-02 0:00 ` William Clodius
1999-02-03 0:00 ` adam
1999-02-03 0:00 ` robert_dewar
1999-02-03 0:00 ` Jean-Pierre Rosen
1999-02-03 0:00 ` Nick Roberts
1999-02-03 0:00 ` William Clodius
1999-02-03 0:00 ` Nick Roberts
1999-02-03 0:00 ` robert_dewar
1999-02-03 0:00 ` Robert A Duff
1999-02-03 0:00 ` robert_dewar
1999-02-02 0:00 ` Wanted: Ada STL. Reward: Ada's Future Brian Rogoff
1999-02-02 0:00 ` robert_dewar
1999-02-04 0:00 ` Ehud Lamm
1999-02-03 0:00 ` John English
1999-02-03 0:00 ` Matthew Heaney
1999-02-03 0:00 ` Brian Rogoff
1999-02-04 0:00 ` Stephen Leake
1999-02-04 0:00 ` Hyman Rosen
1999-02-05 0:00 ` Stephen Leake
1999-02-05 0:00 ` Hyman Rosen
1999-02-04 0:00 ` Matthew Heaney
1999-02-04 0:00 ` Brian Rogoff
1999-02-05 0:00 ` Stephen Leake
1999-02-05 0:00 ` Brian Rogoff
1999-02-05 0:00 ` John English
1999-02-05 0:00 ` Tucker Taft
1999-02-05 0:00 ` Brian Rogoff
1999-02-05 0:00 ` Richard D Riehle
1999-02-05 0:00 ` Brian Rogoff
1999-02-06 0:00 ` Matthew Heaney
1999-02-05 0:00 ` John English
1999-02-05 0:00 ` Nick Roberts
1999-02-04 0:00 ` Ehud Lamm
1999-02-04 0:00 ` Al Christians
1999-02-04 0:00 ` Pat Rogers
1999-02-04 0:00 ` Larry Kilgallen
1999-02-04 0:00 ` Pat Rogers
1999-02-04 0:00 ` Larry Kilgallen
1999-02-05 0:00 ` robert_dewar
1999-02-05 0:00 ` Larry Kilgallen
1999-02-05 0:00 ` Tom Moran
1999-02-05 0:00 ` dewar
1999-02-05 0:00 ` Tom Moran
1999-02-05 0:00 ` dewar
1999-02-05 0:00 ` dennison
1999-02-06 0:00 ` dewar
1999-02-08 0:00 ` dennison
1999-02-08 0:00 ` robert_dewar
1999-02-08 0:00 ` dennison
1999-02-09 0:00 ` robert_dewar
1999-02-09 0:00 ` dennison
1999-02-09 0:00 ` Nick Roberts
1999-02-07 0:00 ` Simon Wright
1999-02-08 0:00 ` Corey Minyard
1999-02-08 0:00 ` Open Source Licensing (was: Wanted: Ada STL. Reward: Ada's Future) dennison
1999-02-08 0:00 ` Corey Minyard
1999-02-09 0:00 ` dennison
1999-02-09 0:00 ` Corey Minyard
1999-02-09 0:00 ` robert_dewar
1999-02-09 0:00 ` Corey Minyard
1999-02-09 0:00 ` Wanted: Ada STL. Reward: Ada's Future robert_dewar
1999-02-09 0:00 ` dennison
1999-02-10 0:00 ` robert_dewar
1999-02-07 0:00 ` Simon Wright
[not found] ` <36ba730b.35540068@ <79fmg1$fn0$1@nnrp1.dejanews.com>
1999-02-06 0:00 ` Larry Kilgallen
1999-02-05 0:00 ` robert_dewar
1999-02-05 0:00 ` robert_dewar
1999-02-05 0:00 ` Larry Kilgallen
1999-02-05 0:00 ` robert_dewar
[not found] ` <79f24e$t14 <36BB4162.52FC6D9F@averstar.com>
1999-02-05 0:00 ` robert_dewar
1999-02-05 0:00 ` dennison
1999-02-05 0:00 ` Tucker Taft
1999-02-05 0:00 ` dennison
1999-02-05 0:00 ` robert_dewar
1999-02-05 0:00 ` dennison
1999-02-06 0:00 ` Nick Roberts
1999-02-04 0:00 ` Brian Rogoff
1999-02-05 0:00 ` Matthew Heaney
1999-02-05 0:00 ` Brian Rogoff
1999-02-08 0:00 ` John English
1999-02-05 0:00 ` John English
1999-02-09 0:00 ` micro_ada
1999-02-05 0:00 ` Nick Roberts
1999-02-08 0:00 ` John English
1999-02-02 0:00 ` Richard D Riehle
1999-02-03 0:00 ` robert_dewar
1999-02-05 0:00 ` Corey Minyard
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox