Re: Basic Properties of Lists

[Jeffrey Carter <jeffrey.carter@boeing.com>]

Ted Dennison wrote:
> 
> In article <3C110606.A37E9D10@boeing.com>, Jeffrey Carter says...
> 
> >Every data structures text I've seen describes the abstract concept of a
> >list as an ordered sequence of values with one value considered the
> >first value, another the next value, and so on to the last value. I
> 
> I'd agree with the first part, but not with the second, at least not for a
> general bidirectional list like we have.
> 
> I know some texts say "linked-list" when they mean "singly-linked-list". Also,
> some authors may not be as careful about using confusing terminology like
> "first" and "last" for ends like we are being. Also, sometimes people come into
> reading with a preconcieved idea about things, and end up not comming away with
> the precise concept that the author intended. And sometimes authors are just
> plain wrong (it happens).

This is not something that depends on an implementation; it is a
property of the abstraction.

> 
> Anyway, I'm not sure where you got this impression. But I can assure you that I
> have been "classicly trained" in Computer Science (BS and MS), have had to read
> many such texts for no less than 5 different courses that covered this kind of
> material, and did not come away with that impression.

Well, I just found a coworker's _Software Components with Ada_, and
Booch also has this as a property of the abstract concept of a list. I'm
not talking about his implementation, but his description of the
abstraction.

> 
> >nor have I found any online. [However, see pp 70 and 72 of file
> >08Pointers.ppt available at
> >
> >http://cs.calvin.edu/books/c++/ds/1e/NewPPSlides2/
> 
> I did take a look at that. He does indeed use the unfortunate labels "First" and
> "Last", which seem to be causing you so much trouble.

It appears from p 72 that the STL also uses this terminology.

They're not causing me any trouble. I thought they were causing you
trouble.

If we can't agree on the basic properties of lists we'll never get
anywhere. Perhaps we need an appeal to authority here. Who do you trust?
Feldman wrote a text on data structures in Ada, and is known to
sometimes comment on things here or in the Team-Ada list. Can we agree
to appeal to him and abide by his expert opinion?

-- 
Jeffrey Carter