Re: List Strawman JC01

[Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov>]

Ted Dennison<dennison@telepath.com> writes:

> In article <3C0FAF78.6F006DF7@boeing.com>, Jeffrey Carter says...
> <snip>
> >> "Next" requires a direction parameter to disambiguate.
> >> The only directional terminology we have at all is "Front" and "Back".
> >
> >These do not apply to this package.
> 
> Ahhh. So what you are saying is that I need to take more of a holistic approach
> on the naming issue. That's a good point. 
> 
> So really the lynchpin in your argument here is that we change our terminology
> from talking about "Front" and "Back" to "First" and "Last". This way we
> arbitrarily assign a direction to what is otherwise a directionless data
> structure, and then terms that rely on the notion of progressing suddenly make
> sense.

I don't think "Front" and "Back" are significantly more
"directionless" than "First" and "Last". "A" and "B" would be more
directionless, although even those have an alphabetical order.

I'd go with "First" and "Last", to be consistent with general Ada
usage. An array is just as directionless as a list, and we are all
used to First, Last, and "reverse" for array iteration.

> I don't think I'd be in favor of that, because that lack of
> direction is really an integral part of a (doubly-linked) list, and
> I don't see directionality gaining us a great deal of anything for
> the loss of flexability. But of course if I turn out to be in the
> minority on this, I'll so change the strawman.
> 
> >I'll ask you to go look at the spec (of List_Strawman_JC01) again. There
> >is a First function, since this is a basic property of a list. There is
> 
> No its not. Its a basic property of a *singly* linked list. For a doubly-linked
> list, there is no logical "first" element, and working from either end is
> equivalent.

Again, I don't see "Front" as significantly different from "First"
here. Both return a well-defined item from one end of a list.
Both imply a cardinal order. And going thru a list from "Last" to
"First" _is_ equivalent to going thru it from "First" to "Last", just
as it is for Ada arrays.

> >The ordering property applies for all lists, regardless of
> >implementation, just as it applies for arrays. An array is sorted
> >in ascending order if no element is less than a preceding element.
> >The fact that you can do > (examples using other data structures
> >deleted) > You can't use examples of *other* data structures to
> >make your point, because > they aren't doubly-linked lists. This
> >reflexive property is what makes a > doubly-linked list different
> >from arrays and singly-linked lists.
> 
> OK. Lets try a thought experiment here. Picture in your mind's eye an array
> rotating slowing in space. You don't have any markers on it; its just a string
> of values. How do you know which is the "first" element? That's easy right? You
> just find the side with the lowest index.

Ok.

> Now lets try the same thought experiment with a singly linked list.
> You've got a string of cells linked with directional arrows rotating
> in space with directional arrows going between them. How do you know
> which is the "first" element? Again, this is easy. Its the element
> that only has an arrow going out of it, and no arrow going into it.

Ok.

> Now lets do the same thing with a doubly-linked list. We have a
> string of cells with bidirectional arrows between them rotating in
> space. Now how do you find which element is the "first" one?
> 
> The answer of course is that you *can't*. 

Ok, but neither can I find the "Front"!

> What we have here is a truly direction-neutral structure. We could
> always go "eeny-meeny-miny-mo" and pick one of course. But just
> because we did that doesn't suddenly make a directional bias
> inherent in the data structure. Its something the user imposes, and
> its there only in as much as the user believes in it and adheres to
> it.

Yes, the user imposes it. What's wrong with calling it "First"? 

I guess you are saying that using "First" implies that the analogy
with arrays is closer than it really is, and you want to make the
differences clearer. I can sympathize with that. But I think the fact
that the name of the package is "List" satisfies that criteria, and
the advantages of using "First" outweigh the harm.

If this were the last thing we had to argue about, we'd be in really
good shape :).

> I'd like to hear from one of the instructors in the audience about
> this. After all, you are the ones who have to teach students data
> structures using this thing.

That's a good idea.

-- 
-- Stephe